算法常用的解题思路---二分查找（Binary search）

Posted by Sunfy on 2021-07-21
Words 1.9k and Reading Time 7 Minutes
Viewed Times
Viewed Times
Visitors In Total

滑动窗口算法其实和这个是一样的，只是用的地方场景不一样，可以根据需要调整窗口的大小，有时也可以是固定窗口大小。

使用二分查找的必要条件

1.必须采用 顺序存储结构

2.必须按关键字大小有序排列

704. 二分查找

给定一个 n 个元素有序的（升序）整型数组 nums和一个目标值 target ，写一个函数搜索 nums 中的target，如果目标值存在返回下标，否则返回-1。

思路

二分查找是一种基于比较目标值和数组中间元素的教科书式算法。

如果目标值等于中间元素，则找到目标值。
如果目标值较小，继续在左侧搜索。
如果目标值较大，则继续在右侧搜索。

image-20210722171024295

算法

1
2
3
4
5
6
初始化指针 left = 0, right = n - 1。
当 left <= right：
比较中间元素 nums[pivot] 和目标值 target 。
如果 target = nums[pivot]，返回 pivot。
如果 target < nums[pivot]，则在左侧继续搜索 right = pivot - 1。
如果 target > nums[pivot]，则在右侧继续搜索 left = pivot + 1。

image-20210722171047184

image-20210722171101779

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int search(int[] nums, int target) {
        // 定义二分查找变量
        int center, left = 0, right = nums.length - 1;
        // 遍历查找数据，找到则返回
        while (left <= right) {
            center = left + (right - left) / 2;
            if (nums[center]  == target) return center;
            if (target < nums[center]) right = center - 1;
            else left = center + 1;
        }
        // 没有找到数据则返回-1
        return -1;
    }
}

复杂度分析

  • 时间复杂度：O(logN)。
  • 空间复杂度：O(1)。

278. 第一个错误的版本

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, …, n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

1
2
3
4
5
6
7
8
9
10
11
12
示例 1：
输入：n = 5, bad = 4
输出：4
解释：
调用 isBadVersion(3) -> false 
调用 isBadVersion(5) -> true 
调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。

示例 2：
输入：n = 1, bad = 1
输出：1

思路及算法

因为题目要求尽量减少调用检查接口的次数，所以不能对每个版本都调用检查接口，而是应该将调用检查接口的次数降到最低。

注意到一个性质：当一个版本为正确版本，则该版本之前的所有版本均为正确版本；当一个版本为错误版本，则该版本之后的所有版本均为错误版本。我们可以利用这个性质进行二分查找。

具体地，将左右边界分别初始化为 1 和 n，其中 n 是给定的版本数量。设定左右边界之后，每次我们都依据左右边界找到其中间的版本，检查其是否为正确版本。如果该版本为正确版本，那么第一个错误的版本必然位于该版本的右侧，我们缩紧左边界；否则第一个错误的版本必然位于该版本及该版本的左侧，我们缩紧右边界。

这样我们每判断一次都可以缩紧一次边界，而每次缩紧时两边界距离将变为原来的一半，因此我们至多只需要缩紧 O(logn) 次。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        // 定义二分查找变量
        int center, left = 1, right = n;
        while (left < right) {
            center = left + (right - left) / 2;
            // 判断center版本是否合格
            if(isBadVersion(center)) {
                right = center;
            } else {
                left = center + 1;
            }
        }
        return left;
    }
}

复杂度分析

  • 时间复杂度：O(log)，其中 n 是给定版本的数量。
  • 空间复杂度：O(1)。我们只需要常数的空间保存若干变量。

35. 搜索插入位置

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
示例 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

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

示例 5:
输入: nums = [1], target = 0
输出: 0

思路与算法

假设题意是叫你在排序数组中寻找是否存在一个目标值，那么训练有素的读者肯定立马就能想到利用二分法在O(logn)的时间内找到是否存在目标值。但这题还多了个额外的条件，即如果不存在数组中的时候需要返回按顺序插入的位置，那我们还能用二分法么？答案是可以的，我们只需要稍作修改即可。

考虑这个插入的位置 pos，它成立的条件为：

image-20210721173000574

其中 nums 代表排序数组。由于如果存在这个目标值，我们返回的索引也是pos，因此我们可以将两个条件合并得出最后的目标：「在一个有序数组中找第一个大于等于target 的下标」。

问题转化到这里，直接套用二分法即可，即不断用二分法逼近查找第一个大于等于target 的下标 。下文给出的代码是笔者习惯的二分写法，ans 初值设置为数组长度可以省略边界条件的判断，因为存在一种情况是target 大于数组中的所有数，此时需要插入到数组长度的位置。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int searchInsert(int[] nums, int target) {
        int center = nums.length, left = 0, right = nums.length - 1;
        while (left <= right){
            int mid = ((right - left) >> 1) + left;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                center = mid;
                right = center - 1;
            }
        }
        return center;
    }
}

复杂度分析

  • 时间复杂度：O(logn)，其中 n 为数组的长度。二分查找所需的时间复杂度为 O(logn)。
  • 空间复杂度：O(1)。我们只需要常数空间存放若干变量。

特别说明

可能出现的死循环问题，二分查找中用＞＞1代替/2居然死循环了

运算符的优先级

image-20210721175714863

加减运算符的优先级大于位运算优先级，所有在使用位运算符时一定要添加括号；

image-20210721180003894

递归解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
	//O(NlogN)：维护一个有序的DP数组，二分查找	
    public int findLengthOfShortestSubarray(int[] arr) {
        int n = arr.length;
        int[] dp = new int[n]; //dp[i] 长度为i的非递减子序列的最后一个值
        Arrays.fill(dp, Integer.MAX_VALUE);
        for(int i : arr) {
            dp[find(dp, i)] = i;
        }
        for(int i = 0; i < n; i++) if(dp[i] == Integer.MAX_VALUE) {
            return arr.length - i;
        }
        return 0;
    }
    // 递归二分查找
    private int find(int[] arr, int target) {
        if(target < arr[0]) {
            return 0;
        }
        if(target > arr[arr.length-1]) {
            return arr.length-1;
        }
        int l = 0, r = arr.length - 1;
        while(l < r) {
            int mid = l + ((r-l)>>1); //移位要加括号，优先级低
            if(arr[mid] > target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}

Copyright 2021 sunfy.top ALL Rights Reserved

...

...

00:00
00:00
FEATURED TAGS
FRIENDS