二、基础算法精讲：二分

1、二分查找-深入理解

Q：返回数组中大于等于 $target$ 第一个数的索引，如果所有数都小于 $target$，则返回 $-1$。

二分查找三种写法：建议使用闭区间写法，比较容易记忆

• 时间复杂度：$O(logn)$
• 空间复杂度：$O(1)$

AcWing 上面的二分模板是使用的左闭右开的写法

闭区间写法

def lower_bound(nums: Link[int], target: int)->int:
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] < target: 
            left = mid + 1
        else: 
            right = mid - 1
    return left   # 或者 right + 1
1
2
3
4
5
6
7
8
9

左闭右开写法

def lower_bound2(nums: Link[int], target: int)->int:
    left, right = 0, len(nums)
    while left < right:
        mid = (left + right) // 2
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left  # 或者right
1
2
3
4
5
6
7
8
9

开区间写法

# 开区间写法
def lower_bound(nums: Link[int], target: int)->int:
    left, right = -1, len(nums)
    while left + 1 < right:
        mid = (left + right) // 2
        if nums[mid] < target:
            left = mid
        else:
            right = mid
    return right  # 或者 left + 1 
1
2
3
4
5
6
7
8
9
10

二分查找四种任务之间转换（查找整数的任务前提下）：所有任务都可以基于第一个任务进行转换

1. 大于等于 $x$（代码如上）
2. 大于 $x$：看成大于等于 $x+1$
3. 小于 $x$：看成大于等于 $x-1$
4. 小于等于 $x$：看成大于 $x-1$

1.1 在排序数组中查找元素的第一个和最后一个位置

Leetcode 34

def lower_bound(nums: List[int], target: int)->int:
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] < target:
            left += 1
        else:
            right -= 1
    return left

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        start = lower_bound(nums, target)
        if start == len(nums) or nums[start] != target:
            return [-1, -1]
        end = lower_bound(nums, target + 1) - 1
        return [start, end]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    int lower_bound(vector<int> &nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return left;
    }

    vector<int> searchRange(vector<int>& nums, int target) {
        int start = lower_bound(nums, target);
        if (start == nums.size() || nums[start] != target) return {-1, -1};
        int end = lower_bound(nums, target + 1) - 1;
        return {start, end};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

• 时间复杂度：$O(logn)$
• 空间复杂度：$O(1)$

2、二分查找-习题课

2.1 寻找峰值

Leetcode 162

题目保证峰值一定存在，因此 $index=nums.size()-1$ 一定在峰值的右边，因此下面代码中 $right=nums.size()-2$。但是 $index=0$ 不一定在峰值左边，有可能为峰值，因为题目中 $nums[-1]=nums[n]=-\infty$，比如有数组 $[3,2,1]$，其中 $3$ 为峰值。

下面的二分算法中，$left$ 指针及其左边表示峰值左边的元素，$right$ 指针及其右边表示峰值以及峰值右边的元素。通过比较 $nums[mid]$ 与 $nums[mid+1]$：

• $nums[mid]<nums[mid+1]$，表示当前元素 $nums[mid]$ 一定在峰值左边，直接 $left++$；
• $nums[mid]>=nums[mid+1]$，表示当前元素 $nums[mid]$ 可能为峰值，也可能在峰值右边，因此 $right--$；

二分结束之后，$nums[left]=nums[right+1]$ 就是其中一个峰值。

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 2
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] < nums[mid + 1]:
                left += 1
            else:
                right -= 1
        return left
1
2
3
4
5
6
7
8
9
10

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int left = 0, right = nums.size() - 2;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < nums[mid + 1]) left += 1;
            else right -= 1;
        }
        return left;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

• 时间复杂度：$O(logn)$
• 空间复杂度：$O(1)$

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

Leetcode 153

这个题建议去看 leetcode 的官方题解，比较容易理解

这个题目要想清楚为什么二分最后就是答案。二分的原始目的是为了查找数组中大于等于 $x$ 的第一个元素。

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 2
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] < nums[-1]:
                right = mid - 1
            else:
                left = mid + 1
        return nums[left]
1
2
3
4
5
6
7
8
9
10

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0, right = nums.size() - 2;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < nums[nums.size() - 1]) right = mid - 1;
            else left = mid + 1;
        }
        return nums[left];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

• 时间复杂度：$O(logn)$
• 空间复杂度：$O(1)$

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

Leetcode 154

这个题中存在重复元素，但是这个题的代码在上一个题中同样能够通过。

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 2
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] < nums[right + 1]:
                right = mid - 1
            elif nums[mid] > nums[right + 1]:
                left = mid + 1
            else:
                right -= 1
        return nums[left]
1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    int findMin(vector<int>& nums) {
        int n = nums.size();
        int left = 0, right = n - 2;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < nums[right + 1]) right = mid - 1;
            else if (nums[mid] > nums[right + 1]) left = mid + 1;
            else right -- ;
        } 
        return nums[left];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

• 时间复杂度：$O(logn)$
• 空间复杂度：$O(1)$

2.4 搜索旋转排序数组

Leetcode 33

解法一：二次二分

使用 $2.2$ 题中的思路找出最小值，然后将数组划分为两部分，再根据 $target$ 与 $nums[n-1]$ 的大小来决定到哪个部分里面将进行二分查找。

class Solution:
    def findMin(self, nums: List[int])->int:
        left, right = 0, len(nums) - 2
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] < nums[-1]:
                right = mid - 1
            else:
                left = mid + 1
        return left

    def lower_bound(self, nums: List[int], left: int, right: int, target: int)->int:
        l0, r0 = left, right
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        if left <= r0 and nums[left] == target:
            return left
        return -1

    def search(self, nums: List[int], target: int) -> int:
        i = self.findMin(nums)
        if target > nums[-1]:
            left, right = 0, i
        else:
            left, right = i, len(nums) - 1
        return self.lower_bound(nums, left, right, target)
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

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

    int lower_bound(vector<int>& nums, int left, int right, int target) {
        int n = nums.size();
        int l0 = left, r0 = right;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        if (left <= r0 && nums[left] == target)
            return left;
        return -1;
    }

    int search(vector<int>& nums, int target) {
        int i = findMin(nums), n = nums.size();
        int left, right;
        if (target > nums[n - 1]) 
            left = 0, right = i;
        else left = i, right = n - 1;
        return lower_bound(nums, left, right, target);
    }
};
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

• 时间复杂度：$O(logn)$
• 空间复杂度：$O(1)$

解法二：一次二分

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        n = len(nums)
        if n == 0: return -1
        if n == 1:
            return 0 if nums[0] == target else -1
        left, right = 0, n - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target: return mid
            if nums[left] <= nums[mid]:  # left 是 有序区间
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
        return -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        if (!n) return -1;
        if (n == 1) return nums[0] == target ? 0 : -1;
        int left = 0, right = n - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target) return mid;
            if (nums[left] <= nums[mid])  // 区间[left, mid] 有序
                (nums[left] <= target && target < nums[mid]) ? right = mid - 1 : left = mid + 1;
            else 
                (nums[mid] < target && target <= nums[right]) ? left = mid + 1 : right = mid - 1;
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

• 时间复杂度：$O(logn)$
• 空间复杂度：$O(1)$