二分查找算法

9.1 搜索插入位置（简单）：二分查找

题目：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。请必须使用时间复杂度为

O(log n)

的算法。

思想：在一个排序数组中寻求目标值，利用二分法就能正好满足复杂度需求，但该题需要返回不存在数组中值的对应索引，因此需要特殊处理：

• 若插入位置为pos，则：nums[pos - 1] < target < nums[pos]
• 最终left的值就是我们需要求得的应该插入的位置或者就是目标值

总结：要能够清晰的理解题意

代码：

class Solution {
    public int searchInsert(int[] nums, int target) {
        //设置二分法的左右指针
        int left = 0;
        int right = nums.length - 1;
​
        //二分查找步骤：左指针小于右指针的情况下循环
        while(left <= right){
            //中间值的求法
            int middle = left + (right - left) / 2;
            //左右指针移动
            if(nums[middle] < target){
                left = middle + 1;
            }else{
                right = middle - 1;
            }
        }
        //最终索引值就是left；
        return left;
    }
}

9.2 搜索旋转排序数组(中等)：二分查找

题目：整数数组

nums

按升序排列，数组中的值 互不相同 。

在传递给函数之前，

nums

在预先未知的某个下标

k

（

0 <= k < nums.length

）上进行了 旋转，使数组变为

[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]

（下标 从 0 开始 计数）。例如，

[0,1,2,4,5,6,7]

在下标

3

处经旋转后可能变为

[4,5,6,7,0,1,2]

。

给你 旋转后 的数组

nums

和一个整数

target

，如果

nums

中存在这个目标值

target

，则返回它的下标，否则返回

-1

。

你必须设计一个时间复杂度为

O(log n)

的算法解决此问题。

思想：原本的数组是升序排列，经过旋转之后，则这道题中给定的数组可以从中心分为两部分，这两部分一定有一部分是有序的，比如:

[4,5,6,7,0,1,2]

，,从

middle

分开为：

[4, 5, 6]

和

[7, 0, 1, 2]

两个部分，其中左边

[4, 5, 6]

这个部分的数组是有序的，然后在使用二分查找

• 由middle分开为两个部分 [l, mid] 和 [mid + 1, r] ，我们查看target位于哪个区间内，然后再在该区间内查找值即可

总结：将旋转后数组从

middle

分为两部分，然后判断

target

的位置

代码：

class Solution {
    public int search(int[] nums, int target) {
        //若数组为空，直接返回-1
        if(nums == null || nums.length == 0){
            return -1;
        }
        //若数组只有一个值，直接判断
        if(nums.length == 1){
            return target == nums[0] ? 0 : -1;
        }
​
        //声明左右指针
        int left = 0;
        int right = nums.length - 1;
​
        //进行二分查找
        while(left <= right){
            int middle = left + (right - left) / 2;
​
            if(nums[middle] == target){
                return middle;
            }
            //若目标值在左区间
            if(nums[0] <= nums[middle]){
                if(nums[0] <= target && target <= nums[middle]){
                    right = middle - 1;
                }else{
                    left = middle + 1;
                }
            }//若目标在右区间
            else{
                if(nums[middle] < target && target <= nums[nums.length - 1]){
                    left = middle + 1;
                }else{
                    right = middle - 1;
                }
            }
        }
        return -1;
    }
}
​
//暴力解法
    public int search(int[] nums, int target) {
        int i = 0;
        for (int num : nums) {
            if (num == target) {
                return i;
            }
            i++;
        }
        return -1;
    }

9.3 搜索旋转排序数组Ⅱ（中等）：二分查找

题目：已知存在一个按非降序排列的整数数组

nums

，数组中的值不必互不相同。

在传递给函数之前，

nums

在预先未知的某个下标

k

（

0 <= k < nums.length

）上进行了 旋转 ，使数组变为

[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]

（下标 从 0 开始 计数）。例如，

[0,1,2,4,4,4,5,6,6,7]

在下标

5

处经旋转后可能变为

[4,5,6,6,7,0,1,2,4,4]

。

给你 旋转后 的数组

nums

和一个整数

target

，请你编写一个函数来判断给定的目标值是否存在于数组中。如果

nums

中存在这个目标值

target

，则返回

true

，否则返回

false

。

你必须尽可能减少整个操作步骤。

思想：不要为了二分查找而进行二分查找，可以存在更优解

总结：要能够清晰的理解题意

代码：

class Solution {
    public boolean search(int[] nums, int target) {
        for(int v : nums){
            if(v == target){
                return true;
            }
        }
        return false;
    }
}

9.4 搜索二维矩阵（中等）：二分查找

题目：给你一个满足下述两条属性的

m x n

整数矩阵：

• 每行中的整数从左到右按非递减顺序排列。
• 每行的第一个整数大于前一行的最后一个整数。

给你一个整数

target

，如果

target

在矩阵中，返回

true

；否则，返回

false

。

思想：将矩阵合并看作为一个升序数组，然后对升序数组进行二分查找

• 我们需要确定的是矩阵中第(i, j)个位置上是否存在target，因此将每次(i, j)位置的值和target相比较即可，若存在相等值说明就存在
• 我们可以发现：数组第(i, j)位置的值可以这样取得：nums[middle / n][midlle % n]；
• 进行二分查找时，我们直接比较(i, j)的值和target大小即可，根据大小移动左右指针，可以将此时的(i, j)当作是一个middle

总结：将矩阵合并为一个升序数组后对应索引的位置求法是很巧妙的，可以多在纸上进行数学验证得出

代码：

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        //得到数组的长与宽
        int m = matrix.length;
        int n = matrix[0].length;
​
        //声明矩阵合并为升序数组后的左右指针
        int low = 0;
        int high = m * n - 1;
​
        //进行二分查找
        while(low <= high){
            int middle = low + (high - low) / 2;
            //矩阵中任意一个元素的值可以表示为：`nums[middle / n][midlle % n]`
            int x = matrix[middle / n][middle % n];
            //比较当前值和target的大小，若当前值小，由于数组升序，将左指针右移
            if(x < target){
                low = middle + 1;
            }//当前值大，右指针左移
            else if(x > target){
                high = middle - 1;
            }else{
                return true;
            }
        }
        return false;
    }
}

9.5 寻找旋转排序数组中的最小值（中等）：二分查找（这个有点绕）

题目：已知一个长度为

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)

的算法解决此问题。

思想：一个升序数组经过旋转后，我们可以发现旋转后的数组的最后一个元素

x

和数组的最小值

min

存在一定关系：

• min右侧的值一定小于x
• min左侧的值一定大于x

通过这一点，运用二分查找可以得出：

• 若nums[middle] < x，说明最小值在middle的左边，可以直接忽略二分查找的右半区间；注意此时应该为： if(nums[middle] <= nums[high]){ high = middle; }- 因为可能middle值就是目标值，若为high = middle - 1;就少了一个值
• 若nums[middle] > x，说明最小值在middle的右边，可以直接忽略二分查找的左半区间

总结：注意到舍去左右区间时的操作，可以举特例理解

代码：

class Solution {
    public int findMin(int[] nums) {
        //声明左右指针
        int low = 0;
        int high = nums.length - 1;
​
        //进行二分查找
        while(low < high){
            int middle = low + (high - low) / 2;
            //此时，说明最小值位于middle的左边，忽略右边区间
            if(nums[middle] <= nums[high]){
                high = middle;
            }else{
                low = middle + 1;
            }
        }
        return nums[low];
    }
}

9.6 x的平方根（简单）：二分查找

题目：给你一个非负整数

x

，计算并返回

x

的 算术平方根 。由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：不允许使用任何内置指数函数和算符，例如

pow(x, 0.5)

或者

x ** 0.5

。

思想：只需在小于

x

的范围之内寻找相乘小于等于

x

的最大值即可，使用二分查找

总结：注意

middle * middle

可能会大于

int

的默认范围，需要将其转为

long

代码：

class Solution {
    public int mySqrt(int x) {
        int low = 0;
        int high = x;
        int res = 0;
​
        while(low <= high){
            int middle = low + (high - low) / 2;
            if((long)middle * middle <= x){
                res = middle;
                low = middle + 1;
            }else{
                high = middle - 1;
            }
        }
        return res;
    }
}

9.7 寻找峰值（中等）：二分查找

题目：峰值元素是指其值严格大于左右相邻值的元素。给你一个整数数组

nums

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

nums[-1] = nums[n] = -∞

。

你必须实现时间复杂度为

O(log n)

的算法来解决此问题。

思想：最大值一定是一个峰值，因此直接寻找最大值即可

总结：最大值一定是峰值，可将该题转换思路进行解决

代码：

class Solution {
    public int findPeakElement(int[] nums) {
        int low = 0;
        int high = nums.length - 1;
​
        while(low < high){
            int middle = low + (high - low) / 2;
            if(nums[middle] <= nums[middle + 1]){
                low = middle + 1;
            }else{
                high = middle;
            }
        }
        return low;
    }
}

9.8 二分法总结！！！

二分法说到底是可能是一个经典的套路框架，但有时候并不容易，当使用二分法求解时，有几点需要极其注意：

1. 比较左右指针的大小是 < 还是 <=，这个要根据题目要求，判断左右边界能否达到相同值
2. 左指针left = middle + 1 或者是 left = middle：这是左边界问题，我们在使用二分法求解时，要根据情况，判断左边界的left值是否需要留到下一次二分时使用
3. 右指针right= middle - 1 或者是 right= middle：这是右边界问题，同样需要根据情况判断有边界的值是否需要留到下一次二分时使用