二分法

  • 数组一般有序，且数组元素无重复，可以考虑使用二分法
  • 时间复杂度：O（logN）

两种写法

1、左闭右闭区间

右指针：right = len(nums) - 1

1
2
3
4
5
6
7
8
9
10
11
12
def search(nums,target):
    left = 0
    right = len(nums)-1	# 左闭右闭区间
    while left <= right：	# 当left=right时，是有意义的
    	mid = left + (right-left)//2	# 防止溢出
        if nums[mid] == target:
            return mid
        if nums[mid] > target:	# 此时mid处肯定不是target，所以right = mid -1
            right = mid -1	
        else:
            left = mid + 1
     return -1

2、左闭右开区间

1
2
3
4
5
6
7
8
9
10
11
12
def search(nums,target):
    left = 0
    right = len(nums)	# 左闭右开区间
    while left < right：	# 当left=right时，没有意义的
    	mid = left + (right-left)//2	# 防止溢出
        if nums[mid] == target:
            return mid
        if num[mid] > target:	
            right = mid	# 因为是开区间，此时right可以使mid
        else:
            left = mid + 1
     return -1

3、左开右开区间

1
2
3
4
5
6
7
8
9
10
11
12
def search(nums,target):
    left = -1
    right = len(nums)	# 左开右开区间
    while left + 1 < right：	# 当left=right时，没有意义的
    	mid = left + (right-left)//2	# 防止溢出
        if nums[mid] == target:
            return mid
        if num[mid] > target:	
            right = mid	# 因为是开区间，此时right可以使mid
        else:
            left = mid
     return -1

L - 1始终是红色；R+1始终是蓝色

刷题

33. 搜索旋转排序数组

  • 题目中数组中的值是互不相同的， 输入的数组nums是将有序数组旋转得来的

思路：

  • 采用二分方法，先找到mid，判断nums[mid] == target?，如果相同直接返回mid
  • 如果不相同，则分为两种情况：
    • mid的左半边区域有序：nums[0]<=nums[mid]
      • 判断target是否在nums[0] ~ nums[mid]区间：if nums[0]<= target < nums[mid]: right = mid -1 else: left = mid + 1
    • mid的右半边区域有序：nums[0]>nums[mid]，则nums[mid] ~ nums[lenn(nums)-1]区间有序
      • 判断target是否在nums[mid] ~ nums[lenn(nums)-1]区间：if nums[mid]< target <= nums[len(nujms)-1]: left = mid + 1 else: right = mid -1
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:
        left = 0
        right = len(nums)-1 # 左闭右闭区间
        while left <= right:
            mid = left + (right-left)//2
            if nums[mid] == target:
                return mid
            if nums[0]<=nums[mid]:   # 说明mid左半边是有序的
                if nums[0]<= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:   # 否则在mid的右半区间是有序的
                if nums[mid]< target <= nums[len(nums)-1]:
                    left = mid + 1
                else:
                    right = mid -1
        return -1

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

  • 数组按非递减顺序排列，其中目标值可能不只一个

思路：

  • 先找第一个目标值：使用二分法查找

    • 注意：返回的值是left指针

  • 第一个值得到后先判断是否是想要的目标值：if start == len(nums) or nums[start] != target: return [-1, -1]

  • 如果第一个值是目标值，则目标元素的最后一个位置一定存在

    • 这里使用二分查找比目标值大1的数的位置
    • 找到该位置后，-1就是目标值的最后一个位置

  • 有序数组中二分查找的四种类型（下面的转换仅适用于数组中都是整数）
    1. 第一个大于等于x的下标： low_bound(x)
    2. 第一个大于x的下标：可以转换为第一个大于等于 x+1 的下标 ，low_bound(x+1)
    3. 最后一个小于x的下标：可以转换为第一个大于等于 x 的下标 的左边位置, low_bound(x) - 1;
    4. 最后一个小于等于x的下标：可以转换为第一个大于等于 x+1 的下标 的 左边位置, low_bound(x+1) - 1;

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
class Solution:
    # 使用二分法找到元素
    def search(selef, nums, target):
        left = 0
        right = len(nums)-1  # 左闭右闭区间
        while left <= right:  # 当left=right时，是有意义的
            mid = left + (right-left)//2  # 防止溢出
            if nums[mid] < target:
                left = mid + 1	# 范围缩小到[mid+1, right]
            else:
                right = mid - 1	# 范围缩小到[left, mid-1]
        return left
    # 左开右开区间，right最终指向答案
    def search2(selef, nums, target):
        left = -1
        right = len(nums)  # 左开右开区间
        while left + 1 < right:  # 当left=right时，没有有意义的
            mid = left + (right-left)//2  # 防止溢出
            if nums[mid] < target:
                left = mid	
            else:
                right = mid	
        return right

    def searchRange(self, nums, target: int):
        if len(nums) == 0:
            return [-1, -1]
        start = self.search(nums, target)
        if start == len(nums) or nums[start] != target:
            return [-1, -1]
        # 如果start存在，则end一定存在
        end = self.search(nums, target+1) - 1
        return [start, end]

287. 寻找重复数

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

  • 该数组并没有说一定有序

  • 1 <= nums[i] <= n

  • 数组的长度限制了数组的元素取值

  • 题目要找的是一个 整数，并且这个整数有明确的范围，所以可以使用「二分查找」。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def find_duplicate(nums):
    left, right = 1, len(nums) - 1
    # 通过计数检查重复数字是在i之前还是之后
    # 如果小于等于i的数字个数也小于等于i，就说明还没遇到重复数字
    # 反之，则说明遇到了重复数字（也可能就是i）

    while left < right:
        mid = (left + right) // 2
        count = 0
        for i in nums:
            if i <= mid:
                count += 1

        if count > mid:
            right = mid
        else:
            left = mid + 1

    return left

162. 寻找峰值

  • 峰值左边的元素都小于它，峰值及峰值右边元素是大于等于它，因此数组随后一位元素一定属于峰值或峰值右边，所以二分区间为[0, n-2]，写成开区间就是(-1, n-1)
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        # 峰值左边设为红色，峰值及峰值右边设为蓝色，则n-1即最后一个位置为蓝色，所以区间范围变成【0，n-2】
        # 闭区间[0，n-2]转换成开区间就是[-1,n-1]
        l = -1
        r = len(nums)-1
        while l+1  < r:
            mid = l + (r-l)//2
            if nums[mid]>nums[mid+1]:   # mid右半边都是蓝色
                r = mid
            else:   # mid左半边都是红色
                l = mid
        return r

240. 搜索二维矩阵 II

image-20240314155922599

  • 方法1：从矩阵左下角元素matrix[i,j] 进行二分查找。

    • 如果 matrix[i,j]==target，则找到该元素；
    • 如果matrix[i,j] < target，说明该元素第j列元素都小于target，所以 j += 1；
    • 如果matrix[i,j] > target，说明该元素第j列元素都大于target，所以 i -= 1；

  • 方法二：先取矩阵的第一行，然后在该行进行二分查找target，没有找到就取第二行元素进行二分查找，依次遍历矩阵。该方法最坏情况的时间复杂度为 O(MlogN)

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
37
38
39
40
41
42
43
# 法一：时间复杂度：O(logN)；空间复杂度：O(1)
class Solution:
    def searchMatrix(self, matrix, target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        # 从左下角元素开始进行二分
        i = m-1
        j = 0
        # 什么时候结束，while i>=0 and j<n
        while i >= 0 and j < n:
            if matrix[i][j] == target:
                return True
            elif matrix[i][j] < target:
                j += 1
            else:
                i -= 1
        return False

# 法二：时间复杂度：最坏O(MlogN)；空间复杂度：O(1)

def search(arr, target):
    l = 0
    r = len(arr)-1
    while l <= r:
        mid = (l+r)//2
        if arr[mid] == target:
            return True
        elif arr[mid] > target:
            r = mid - 1
        else:
            l = mid + 1
    if l < len(arr) and arr[l] == target:
        return True
    else:
        return False

class Solution2:
    def searchMatrix(self, matrix, target: int) -> bool:
        m, n = len(matrix), len(matrix[0])    # m = 5, n = 5
        for i in range(m):
            if search(matrix[i], target):
                return True
        return False

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

  • 数组元素互不相同，且升序排列

  • 思路：首先找到中间值mid，比较nums[mid] 和 nums[-1]，如果nums[mid] > nums[-1]，表明mid最小值不在左边区间，此时移动左指针 l = mid +1；如果nums[mid] <= nums[-1], 表明mid右边区间是顺序的，因此找最小值需要右指针往左缩：r = mid-1；当l>r时结束循环，返回num[l]为答案

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