本篇博客给大家带来的是二分查找的知识点,通过相关的OJ题进一步理解二分查找的应用与本质.
🐎文章专栏: 优先算法
🚀若有问题 评论区见
❤ 欢迎大家点赞 评论 收藏 分享
如果你不知道分享给谁,那就分享给薯条.
你们的支持是我不断创作的动力 .

要开心

要快乐

顺便进步

1. 二分查找算法

1.1 二分查找(easy)

题目链接: 704. 二分查找
题目描述:
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

解法1: 暴力枚举

定义变量i,从0开始遍历数组nums,当[i] == target时, return i; 时间复杂度为O(N) , i 每移动一次, 就排除nums中的一个元素.这样效率太低, 那能不能每次移动就排除掉两个或者更多元素,实现对暴力枚举的优化呢?

解法2: (朴素)二分查找
二分查找算法须知: 由题目例子可知, 从target位置处可以把数组分成两段, 说明数组具有二段性, 可以用二分查找算法.

利用数组的单调性, 二分查找能够快速地缩小目标值所在的区间. 从而达到优化暴力枚举的目的, 此法时间复杂度为O(log2N)

1. 具体步骤:
a. 定义 left ， right 指针，分别指向数组的左右区间。
b. 找到待查找区间的中间点 mid ，找到之后分三种情况讨论：

i. arr[mid] == target 说明正好找到，返回 mid 的值；
ii. arr[mid] > target 说明 [mid, right] 这段区间都是大于 target 的，因此舍去右边区间，在左边 [left, mid -1] 的区间继续查找，即让 right = mid - 1 ，然后重复 b 过程；
iii. arr[mid] < target 说明 [left, mid] 这段区间的值都是小于 target 的，因此舍去左边区间，在右边 [mid + 1, right] 区间继续查找，即让 left = mid + 1 ，然后重复 b 过程；

c. 当 left 与 right 错开时，说明整个区间都没有这个数，返回 -1 。

2. 细节处理:
循环条件为什么是 left <= right 而不是 left < right?
极端情况下, 当数组只有一个元素时, 如果循环条件是left < right, 就不会进入循环进行判断了. 所以left <= right才是正确的.

3. 代码实现:

class Solution {
    public int search(int[] nums, int t) {
        int left = 0,right = nums.length-1;
        int mid = 0;
        while(left <= right) {
            //从数组下标上看,left向前移动 一半数组长度的距离走到中间节点.
            mid = left + (right - left)/2;//这么写是为了防止数据量过大直接加导致溢出.
            if(nums[mid] < t) left = mid+1;
            else if(nums[mid] > t) right = mid-1;
            else return mid;
        }
        return -1;
    }
}

总结: 在有序情况下用二分算法求解还是比较方便的, 核心就是 b 步骤, 通过画图推导出 [mid]的情况是必要的.

1.2 在排序数组中查找元素的第⼀个和最后⼀个位置（medium）

题目链接: 34. 在排序数组中查找元素的第一个和最后一个位置
题目描述:

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

解法一: 暴力枚举
定义一个i变量, 从0开始遍历, 第一次遍历 找到目标值的起始位置begin, 第二次遍历找到目标值的结束位置end. return new int[]{begin,end}; 时间复杂度为O(N), 超时!!!

解法二: (边界)二分查找
1. 思路:

还是用二分思想，就是根据数据的性质，在某种判断条件下将区间一分为二，然后舍去其中一个区间，然后再另一个区间内查找；方便叙述，用 x 表示该目标元素， resLeft 表示左边界， resRight 表示右边界。

2. 具体步骤及细节

寻找左边界思路：

• 寻找左边界：
•我们注意到以左边界划分的两个区间的特点：
•左边区间 [left, resLeft - 1] 都是小于 x 的；
•右边区间（包括左边界） [resLeft, right] 都是大于等于 x 的；
•因此，关于 mid 的落点，我们可以分为下面两种情况：
•当我们的 mid 落在 [left, resLeft - 1] 区间的时候，也就是 arr[mid] <
target 。说明 [left, mid] 都是可以舍去的，此时更新 left 到 mid + 1 的位置，继续在 [mid + 1, right] 上寻找左边界；
•当 mid 落在 [resLeft， right] 的区间的时候，也就是 arr[mid] >= target 。
说明 [mid + 1, right] （因为 mid 可能是最终结果，不能舍去）是可以舍去的，此时更新 right 到 mid 的位置，继续在 [left, mid] 上寻找左边界；
• 由此，就可以通过二分，来快速寻找左边界；

寻找左边界的细节处理:

注意：这里找中间元素需要向下取整, 即 mid = left + (mid - left) / 2;
因为后续移动左右指针的时候：
• 左指针： left = mid + 1 ，是会向后移动的，因此区间是会缩小的；
• 右指针： right = mid ，可能会原地踏步比如：如果向上取整的话(mid = left + (mid - left + 1) / 2;) 恰好剩下 两个元素的情况下， left = 0 ， right = 1 ， mid = 1。更新区间之后， left，right，mid 的值没有改变，就会陷入死循环).
因此一定要注意，当 right = mid 的时候，要向下取整。

寻找右边界思路：

• 寻右左边界：
• 用 resRight 表示右边界；
• 我们注意到右边界的特点：
▪ 左边区间 （包括右边界） [left, resRight] 都是小于等于 x 的；
▪ 右边区间 [resRight+ 1, right] 都是大于 x 的；
• 因此，关于 mid 的落点，我们可以分为下⾯两种情况：
• 当我们的 mid 落在 [left, resRight] 区间的时候，说明 [left, mid - 1]
（ mid 不可以舍去，因为有可能是最终结果） 都是可以舍去的，此时更新 left 到 mid的位置； 当 mid 落在 [resRight+ 1, right] 的区间的时候，说明 [mid, right] 内的元素是可以舍去的，此时更新 right 到 mid - 1 的位置；
• 由此，就可以通过⼆分，来快速寻找右边界；

寻找右边界的细节处理:

注意：这里找中间元素需要向上取整。(mid = left + (mid - left + 1) / 2;)
因为后续移动左右指针的时候：
• 左指针： left = mid ，可能会原地踏步（比如：如果向下取整的话，如果剩下 两个元素， left = 0， right = 1，mid = 1 。更新区间之后， left，right，mid 的值没有改变，就会陷入死循环）。
• 右指针： right = mid - 1 ，是会向前移动的，因此区间是会缩小的；
因此⼀定要注意，当 right = mid 的时候，要向下取整。

循环条件都是 left < right, 代入具体例子就能求证出来了. 或者这么想, 当left = right 时, left 就是所要求的下标了, 没有必要再进行一次二分了.

3. 代码实现

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left = 0,right = nums.length-1;
        int[] ret = new int[2];
        ret[0] = ret[1] = -1;
        if(nums.length == 0) return ret;
        //寻找左边界
        while(left < right) {
            int mid = left + (right - left)/2;
            if(nums[mid] < target) {
                left = mid+1;
            }else {
                right = mid;
            }
        }
        //判断nums 中是否存在target
        if(nums[left] == target) {
            ret[0] = left;
        }else {
            return ret;
        }
        //将left和right 放回起始位置.
        left = 0;
        right = nums.length-1;
        while(left < right) {
            int mid = left + (right - left + 1)/2;
            if(nums[mid] <= target) {
                left = mid;
            }else {
                right = mid-1;
            }
        }
        ret[1] = left;
        return ret;
    }
}

总结:
在求 mid 的时候，只有 right = mid - 1 的情况下，才会向上取整 mid = left + (mid - left + 1) / 2. 简单来记, 就是一减一加.

1.3 搜索插入位置

题目链接: 35. 搜索插入位置
题目描述:

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

解法一: 暴力枚举
从0下标开始遍历, 找到满足 [i] <= target 的 i 位置即可, 时间复杂度为O(N), 超时!!!

解法二: 二分查找

1. 验证二段性:

2. 具体步骤:
a. 分析插入位置左右两侧区间上元素的特点：
设插入位置的坐标为 index ，根据插入位置的特点可以知道：
• [left, index] 内的所有元素均是小于等于 target 的；
• [index+1, right] 内的所有元素均是大于 target 的。

b. 设 left 为本轮查询的左边界， right 为本轮查询的右边界。根据 mid 位置元素的信
息，分析下一轮查询的区间：
▪ 当 nums[mid] > target 时，说明 mid 落在了 [index+1, right] 区间上，[mid] 不可能是目标值，所以我们接下来查找的区间在 [left, mid-1] 上。因此，更新 right 到 mid-1 位置，继续查找。
▪ 当 nums[mid] <= target 时，说明 mid 落在了 [left, index] 区间上，
mid 右边但包括 mid 本身，可能是目标值，所以我们接下来查找的区间在 [mid
, right] 上。因此，更新 left 到 mid 的位置，继续查找。

c. 直到我们的查找区间的长度变为 1 ，也就是 left == right 的时候， left 或者
right 所在的位置就是我们要找的结果。

3. 代码实现:

class Solution {
    public int searchInsert(int[] nums, int target) {
        //边界情况考虑:
        if(target < nums[0]) {
            return 0;
        }else if(target > nums[nums.length-1]) {
            return nums.length;
        }
        //二分查找
        int left = 0,right = nums.length-1;
        while(left < right) {
            int mid = left + (right-left+1)/2;
            if(nums[mid] <= target) {
                left = mid;
            }else {
                right = mid-1;
            }
        }
        //判断
        if(nums[left] == target) {
            return left;
        }else {
            return left+1;
        }
    }
}

1.4 x的平方根

题目链接: 69. x 的平方根
题目描述:

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：

输入：x = 4
输出：2
示例 2：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842…, 由于返回类型是整数，小数部分将被舍去。
解法一: 暴力枚举
从1开始遍历到x, 找到 i^i <= x的最后一个i, 返回即可. 时间复杂度为O(N)

解法二: 二分查找
1. 验证二段性:

2. 步骤分析图:

3. 代码实现:

class Solution {
    public int mySqrt(int x) {
        if(x < 1) return 0;
        long left = 1,right = x;
        while(left < right) {
            long mid = left + (right-left+1)/2;
            long tmp = mid*mid;
            if(tmp <= x){
                left = mid;
            }else{
                right = mid-1;
            }
        }
        return (int)left;
    }
}

1.5 山脉数组的峰顶索引ont>

题目链接: 852. 山脉数组的峰顶索引
题目描述:

给定一个长度为 n 的整数 山脉 数组 arr ，其中的值递增到一个 峰值元素 然后递减。

返回峰值元素的下标。

你必须设计并实现时间复杂度为 O(log(n)) 的解决方案。

示例 1：

输入：arr = [0,1,0]
输出：1
示例 2：

输入：arr = [0,2,1,0]
输出：1
示例 3：

输入：arr = [0,10,5,2]
输出：1

解法一: 暴力枚举
遍历数组, 找到数组中元素值最大的下标maxIndex, return maxIndex即可. 时间复杂度为O(N),超时!!!

解法二: 二分查找
1. 验证二段性

2. 步骤分析图:

3. 代码实现:

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int left = 0,right = arr.length-1;
        while(left < right) {
            int mid = left + (right - left + 1)/2;
            if(arr[mid] > arr[mid-1]) {
                left = mid;
            }else {
                right = mid-1;
            }
        }
        return left;
    }
}

1.6 寻找峰值ont>

题目链接: 162. 寻找峰值
题目描述:

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

示例 1：

输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。
示例 2：

输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5
解释：你的函数可以返回索引 1，其峰值元素为 2；
或者返回索引 5， 其峰值元素为 6。

此题根上题一模一样,不做过多讨论, 当成练习, 练一练即可.

1.7 寻找旋转排序数组中的最小值

题目链接: 153. 寻找旋转排序数组中的最小值
题目描述:

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
示例 2：

输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 3 次得到输入数组。
示例 3：

输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。

解法一: 暴力枚举

从0开始遍历数组, 找到最小值的下标. 时间复杂度为O(N), 超时!!!

解法二: 二分查找
1. 验证二段性:

2. 步骤分析图:

3. 细节处理:
在验证二段性的时候, 也可以选取A点将旋转数组划分为两段, 但是这种方式, 处理不了单调递增的特殊情况, 需要额外分析, 但是选取D点分段的方式可以处理单调递增的情况, 所以D点的方式更方便. 具体为什么D点分段能够处理, 举个具体例子走一遍过程就知道了.

4. 代码实现:

class Solution {
    public int findMin(int[] nums) {
        int left = 0,right = nums.length-1;
        int t = nums[right];
        while(left < right) {
            int mid = left + (right-left)/2;
            if(nums[mid] > t) {
                left = mid + 1;
            }else {
                right = mid;
            }
        }
        return nums[left];
    }
}

1.8. 点名

题目链接: LCR 173. 点名
题目描述:

某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于升序数组 records。假定仅有一位同学缺席，请返回他的学号。

示例 1:

输入: records = [0,1,2,3,5]
输出: 4
示例 2:

输入: records = [0, 1, 2, 3, 4, 5, 6, 8]
输出: 7

解法一:

1. 哈希表法
2. 直接遍历找结果
3. 异或运算
4. 数学法, 0~n-1等差数列求和 - 原数组
时间复杂度都是O(N)

解法二: 二分查找
1. 验证二段性

2. 步骤分析图:

3. 代码实现

class Solution {
    public int takeAttendance(int[] records) {
        int left = 0,right = records.length-1;
        while(left < right) {
            int mid = left + (right-left)/2;
            if(records[mid] == mid) {
                left = mid+1;
            }else {
                right = mid;
            }
        }
        //判断是否是极端情况.
        if(records[records.length-1] == records.length-1) {
            return left+1;
        }else {
            return left;
        }
    }
}

综上所述, 二分查找的代码非常好写, 比双指针算法要方便得多, 总结一句话: 能用二分就不用双指针.

本篇博客到这里就结束啦, 感谢观看 ❤❤❤

🐎期待与你的下一次相遇😊😊😊