算法训练之 -- 二分查找

1 二分查找

1. 思路

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

二分存在两种搜索的方法，（1）左闭右闭，（2）左闭右开。尽量使用一种写法，推荐使用第一种。

左闭右闭：right的长度为 len(nums) - 1，while 循环中的判断为 left<=right，并且当更新right的长度时，使用mid - 1。

左闭右开：right的长度为 len(nums)，while 循环中的判断为 left<right，并且当更新right的长度时，使用mid。

2. 解法

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l = 0
        r = len(nums) - 1
        while l <= r:      # 左闭右闭
            mid = (l+r)//2
            if nums[mid] == target:
                return mid
            if nums[mid] > target:
                r = mid - 1
            if nums[mid] <target:
                l = mid + 1
                
        return -1

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        while(l<=r){ 					// 左闭右闭
            int mid = l + (r - l) / 2;
            if(nums[mid] > target){
                r = mid - 1;
            }
            if(nums[mid] < target){
                l = mid + 1;
            }
            if(nums[mid] == target){
                return mid;
            }
        }
        return -1;
    }
};

3. 变种

(1) 题目：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。35. 搜索插入位置 - 力扣（LeetCode）

由于数组中可能存在没有target的情况，而这种情况需要返回target可以插入的索引。

如果while(l<=r) 则我们需要改变 l 的索引， 如果使用第二种二分while(l<r)，则不需要做出改变。

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 第一种二分
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        l = 0
        r = len(nums) - 1
        while l <= r:
            mid = l + (r - l) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] > target:
                r = mid - 1
            if nums[mid] < target:
                l = mid + 1		# 改变 l 的索引，否则遇到 l = r 时回进入死循环
        return l

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 第二种二分
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int l = 0, r = nums.size();
        while(l < r){					// l < r 则不会遇到死循环的情况
            int mid =  l + (r - l) / 2;
            if(nums[mid] == target)
                return mid;
            if(nums[mid] > target)
                r = mid;
            if(nums[mid] < target)
                l = mid + 1;
        }
        return l;
    }
};

(2) 题目:给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

思路：寻找target的起始位置和结束位置。其实就是从左边开始二分查找，找到第一个target，letfidx = mid, r = mid - 1；然后从右边开始二分，找到最后一个target，rightidx = mid, l = mid + 1。

Python

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
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        l, r = 0, len(nums) - 1
        left = right = -1
        while(l <= r):
            mid = (l + r) // 2
            if nums[mid] == target:
                left = mid
                r = mid - 1 # 寻找第一个target，需要往左边移动 ！！！
            if nums[mid] < target:
                l = mid + 1
            if nums[mid] > target:
                r = mid - 1
        # left 定位好了

        l = left if left != -1 else 0
        r = len(nums) - 1
        while(l <= r):
            mid = (l + r) // 2
            if nums[mid] == target:
                right = mid
                l = mid + 1
            if nums[mid] < target:
                l = mid + 1
            if nums[mid] > target:
                r = mid - 1

        return [left, right]

C++

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
35
36
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        int left = -1, right = -1;
        while(l<=r){
            int mid = (l + r) / 2;
            if(nums[mid] == target){
                left = mid;
                r = mid - 1;
            }
            if(nums[mid] < target)
                l = mid + 1;
            if(nums[mid] > target)
                r = mid - 1;
        }

        l = (left != -1) ? left : 0;
        r = nums.size() - 1;
        while(l <= r){
            int mid = (l + r) / 2;
            if(nums[mid] == target){
                right = mid;
                l = mid + 1;
            }
            if(nums[mid] < target)
                l = mid + 1;
            if(nums[mid] > target)
                r = mid - 1;
        }

        vector<int> ans{left, right};

        return ans;
    }
};

(3) 题目： 给你一个非负整数 x ，计算并返回 x 的 算术平方根 。由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。69. x 的平方根 - 力扣（LeetCode）

思路：由于不能使用math函数库，因此可以使用二分的方法，通过mid**2来判断，从而得到ans的值。因为 \(k^2 <= x\) ，所以通过二分查找来找到 k，然后通过移动左右边界来定位 mid。

Python

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def mySqrt(self, x: int) -> int:
        l, r, ans = 0, x, -1
        while l <= r:
            mid = l + (r - l) // 2	# 防止溢出
            if mid ** 2 <= x:	# 定位k
                ans = mid
                l = mid + 1
            else:
                r = mid - 1
        return ans

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int mySqrt(int x) {
        int l = 0, r = x, ans = -1;
        while(l <= r){
            int mid = l + (r - l) / 2;	 // 防止溢出
            if((long long )mid * mid <= x){ // 大数 需要长整型
                ans = mid;
                l = mid + 1;
            }else{
                r = mid - 1;
            }
        }
        return ans;
    }
};

(4) 题目：给你一个满足下述两条属性的 m x n 整数矩阵：

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

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。74. 搜索二维矩阵 - 力扣（LeetCode）

思路：对于二维有序的矩阵，进行元素搜索时也可以使用二分。可以使用二次二分进行查找，也可以使用一次二分进行查找。

  • 两次二分查找：就是先对行或列进行查找，确定元素在哪列或行，然后对确定的那列或行进行第二次查找，最终找到元素。
  • 一次二分查找：就是将二维矩阵看为一维数组，通过取整取余操作来判断元素位置，mid / n 为元素的行，mid % n 为元素列（因为每n个元素后才会换行）

Python

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
# 两次二分
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        n = len(matrix[0]) - 1# 列
        m = len(matrix) - 1 # 行
        top = 0
        left = 0
        while top <= m:
            mid = top + (m - top) // 2
            # if matrix[mid][left] == target:
            #     return True
            if matrix[mid][left] < target:
                top = mid + 1
            elif matrix[mid][left] > target:
                m = mid - 1
            else:
                return True
        top -= 1
        while left <= n:
            mid = left + (n -left) // 2
            # if matrix[top][mid] == target:
            #     return True
            if matrix[top][mid] < target:
                left = mid + 1
            elif matrix[top][mid] > target:
                n = mid - 1
            else:
                return True 
        return False

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 一次二分
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        int n = matrix[0].size();
        int left = 0, right = m * n - 1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(matrix[mid / n][mid % n] > target){
                right = mid - 1;
            }else if (matrix[mid / n][mid % n] < target){
                left = mid + 1;
            }else {
                return true;
            }
        }
        return false;
    }
};

(5) 题目：在传递给函数之前，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) 的算法解决此问题。33. 搜索旋转排序数组 - 力扣（LeetCode）

思路：在常规二分查找的时候查看当前 mid 为分割位置分割出来的两个部分 [l, mid] 和 [mid + 1, r] 哪个部分是有序的，并根据有序的那个部分确定我们该如何改变二分查找的上下界，因为我们能够根据有序的那部分判断出 target 在不在这个部分：

  • 如果 [l, mid - 1] 是有序数组，且 target 的大小满足 [nums[l],nums[mid])，则我们应该将搜索范围缩小至 [l, mid - 1]，否则在 [mid + 1, r] 中寻找。

  • 如果 [mid, r] 是有序数组，且 target 的大小满足 (nums[mid+1],nums[r]]，则我们应该将搜索范围缩小至 [mid + 1, r]，否则在 [l, mid - 1] 中寻找。

PS：一定要注意等号的问题。

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1
        while l <= r:
            mid = l + (r - l) // 2
            if nums[mid] == target:
                    return mid
            elif nums[l] <= nums[mid]:
                if nums[l] <= target and target < nums[mid]:	# 左等号
                    r = mid - 1
                else:
                    l = mid + 1
            else:
                if nums[mid] < target and target <= nums[r]:	# 右等号
                    l = mid + 1
                else:
                    r = mid - 1
        return -1

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        while(l <= r){
            int mid = l + (r - l) / 2;
            if(nums[mid] == target)
                return mid;
            else if(nums[l] <= nums[mid]){
                if(nums[l] <= target && target < nums[mid])	 // 注意等号
                    r = mid - 1;
                else
                    l = mid + 1;
            }else{
                if(nums[mid] < target && target <= nums[r])	 // 注意等号
                    l = mid + 1;
                else
                    r = mid - 1;
            }
        }
        return -1;
    }
};
算法
#刷题
算法训练之 -- 二分查找
http://seulqxq.top/posts/42877/
作者
SeulQxQ
发布于
2023年12月7日
许可协议