leetcode 二分查找

算法
, ,

二分查找要求线性表必须采用顺序存储结构，而且表中元素按关键词有序排列。 时间复杂度为 o(log(n))

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
def binary_search(search_list, search_key):
    low = 0
    high = len(search_list) - 1
    while(low <= high):
        mid = low + (high-low)//2  #1#2
        print(mid)
        if(search_key == search_list[mid]):
            return mid
        elif(search_key < search_list[mid]):
            high = mid - 1
        else:
            low = mid + 1
    return -1

需要注意的事项：

  1. 计算 mid 时，使用其它语言（JAVA,C++）编写时，若采用 (low+high)//2 时存在溢出风险，int 最大值为 65535，超过后会变为负值，但 python 中不存在整数溢出问题；
  2. python3 中除法，/ 为真除法，带小数位，// 取整数位

二分查找变种

  1. 找第一个，都是返回 left。 找第一个等于，第一个大于等于，判断条件为 if nums[mid] >= target; 第一个大于，判断条件为 if nums[mid] > target
  2. 找最后一个，都是返回 right。 找最后一个等于，最后一个小于等于，判断条件为 if nums[mid] <= target; 最后一个小于，判断条件为 if nums[mid] < target
  3. 注意都需要进行边界判断，找不到返回 -1。 循环终止的时候，left < len(nums), right >= 0, 找相等的时候还需要判断 nums[left] 或 nums[right] 是否会等于 target

有重复数字，找第一个和最后一个与 target 相等的下标

Find First and Last Position of Element in Sorted Array

Leetcode : 34. Find First and Last Position of Element in Sorted Array (Medium)

时间复杂度为 O(logn)，如果先找到一个 index，再往前往后查找的话，当全部都是一样的数字时，时间会退化为 O(n)
因此需要直接用二分查找找出，需要修改条件。跳出条件为 left<=right，到最后 right=left+1, left 可能会越界

  1. 判断返回 left 还是 right。 当第一个等于 target 的元素，返回 left，找最后一个等于 target 的元素返回 right
  2. 判断 if target ? nums[mid] 这里的符号。 返回第一个等于 target 的元素，需要向左逼近，因此当 target <= nums[mid] 时，让 right = mid - 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def searchRange(self, nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right-left) // 2
        if nums[mid] >= target: # 注意此处的条件
            right = mid - 1
        else:
            left = mid + 1
    if left >= len(nums) or nums[left] != target: # 注意此处的条件
        return [-1, -1]
    l = left

    right = len(nums) - 1
    while left <= right:
        mid = left + (right-left) // 2
        if nums[mid] <= target: # 注意此处的条件，如果只是单独返回最后一个相等的元素，还是需要判断一下 right >= 0 and nums[right] == target
            left = mid + 1
        else:
            right = mid - 1
    return [l, right]

返回第一个大于等于 target 的元素，或返回最后一个小于等于 target 的元素

第一个大于等于 target：

1
2
3
4
5
6
7
8
9
def binarySearch(nums, target):
    left, right = 0, len(nums)-1
    while left <= right:
        mid = left + (right-left) // 2
        if nums[mid] >= target:  # 若找第一个大于 target 的，只需要改成 >
            right = mid - 1
        else:
            left = mid + 1
    return left if left < len(nums) else -1

最后一个小于等于 target：

1
2
3
4
5
6
7
8
9
def binarySearch(nums, target):
    left, right = 0, len(nums)-1
    while left <= right:
        mid = left + (right-left) // 2
        if nums[mid] <= target: # 若找第一个小于 target 的，只需要改成 <
            left = mid + 1
        else:
            right = mid - 1
    return right if right >= 0 else -1

Leetcode 刷题

Median of Two Sorted Arrays

Leetcode : 4. Median of Two Sorted Arrays (Hard)

Search in Rotated Sorted Array

Leetcode : 33. Search in Rotated Sorted Array (Medium)

在一个 rotate 的数组中找到目标数字的下标，但不知道 rotate 的位置在哪里，要求时间复杂度为 O(logn)，显然是二分查找。
利用二分查找来判断左右两边哪边的序列是有序的，若 nums[mid] 大于 nums[left]，则左边是有序的，若 nums[mid] 小于 nums[right]，则右边是有序的。
之后根据有序的半段来判断 num[mid] 是否在该区域中，来调整边界。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def search(self, nums, target):
    left = 0
    right = len(nums)-1
    while left <= right:
        mid= left + (right-left) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] >= nums[left]:
            if target >= nums[left] and target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        elif nums[mid] <= nums[right]:
            if target <= nums[right] and target > nums[mid]:
                left = mid + 1
            else:
                right = mid - 1
    return -1

Search in Rotated Sorted Array II

Leetcode : 81. Search in Rotated Sorted Array II (Medium)

与 33 不同的是，该题的数组可能有重复元素。 投机做法： return target in nums
该题比 33 多了一种情况，即可能出现 nums[mid] == nums[left], 此时无法判断 target 会在哪一边，因此只能够 left+1 往前走。其余的情况和上一题类似。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def search(self, nums, target):
    left = 0
    right = len(nums)-1
    while left <= right:
        mid = left + (right-left) // 2
        if nums[mid] == target:
            return True
        elif nums[mid] == nums[left]:
            left += 1
        elif nums[mid] < nums[left]:
            if target > nums[mid] and target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
        else:
            if target < nums[mid] and target >= nums[left]:
                right = mid - 1
            else:
                left = mid + 1
    return False

Find First and Last Position of Element in Sorted Array

Leetcode : 34. Find First and Last Position of Element in Sorted Array (Medium)

思路：先二分搜索找到位置，再根据该位置 index，循环判断 nums[index-1] 和 nums[index+1] 是否和 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
def searchRange(self, nums, target):
    left = 0
    right = len(nums)-1
    index = -1
    while left <= right:
        mid = left + (right-left) // 2
        if nums[mid] == target:
            index = mid
            break
        elif target > nums[mid]:
            left = mid + 1
        else:
            right = mid - 1

    if index != -1:
        i = index - 1
        j = index + 1
        while i>=0 and nums[i] == target:
            i -= 1
        while j <= len(nums)-1 and nums[j] == target:
            j += 1
        return [i+1, j-1]
    else:
        return [-1, -1]

求开方

Leetcode : 69. Sqrt(x) (Easy)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def my_sqrt(x):
    if x<=1:
        return x
    elif x>1:
        low = 1
        high = x
        while (low <= high):
            mid = low + (high-low)//2
            sqrt = x // mid
            if sqrt == mid :
                return mid
            elif sqrt > mid:
                low = mid + 1
            else:
                high = mid - 1
        return high  #1
    else:
        return -1

备注：

  1. 一个数 x>1 的开方必定在 1~x 之间，因此可以用二分查找来找到 sqrt
  2. 由于返回的是整数，因此开方包含小数位时，找不到 sqrt==mid ，则返回开方的整数位

矩阵查找 Search a 2D Matrix

Leetocde : 74. Search a 2D Matrix (Medium)

矩阵查找 Search a 2D Matrix II

Leetocde : 240. Search a 2D Matrix II (Medium)

这两题的做法是一样的。

思路：题中要求的有效率的算法，很容易想到二分查找和分治两种方法

  1. 二分查找
    用二分查找求解需要进行两次二分查找，首先二分查找出 target 所在的行范围，再遍历每一行，二分查找出 target 的位置。最坏情况下的时间复杂度为 o(nlogn)
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
def searchMatrix(matrix, target):
    if not matrix or not matrix[0]:
        return False
    low = 0
    high = len(matrix)-1
    while low+1 < high:
        mid = low + (high-low)//2
        if matrix[mid][0] == target:
            return True
        elif target > matrix[mid][0]:
            low = mid
        else:
            high = mid - 1
    row = high if matrix[high][0] <= target else low
    
    left = 0
    right = len(matrix[0])-1
    while left <= right:
        mid = left + (right-left)//2
        if matrix[row][mid] == target:
            return True
        elif target > matrix[row][mid]:
            left = mid + 1
        else:
            right = mid - 1
    return False
  1. 分治法（选择该做法）

该有序矩阵即按行递增也按列递增，因此可以考虑右上角的数字，若 target > 15，则直接去掉该行，row–；若 target < 15，则去掉该列，column–；此时将原本的二维矩阵变成了更小的矩阵。时间复杂度为 o(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
def searchMatrix(matrix, target):
    if not matrix or not matrix[0]:
        return False
    row = 0
    col = len(matrix[0]) - 1
    while row < len(matrix) and col >= 0:
        if target == matrix[row][col]:
            return True
        elif target > matrix[row][col]:
            row += 1
        else:
            col -= 1
    return False

Find Minimum in Rotated Sorted Array

Leetcode : 153. Find Minimum in Rotated Sorted Array (Medium)

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

Find Minimum in Rotated Sorted Array II

Leetcode : 154. Find Minimum in Rotated Sorted Array II (Hard)

  • 当 nums[mid] > nums[right]，则 min 肯定是右半部分，而且不可能是 mid， 所以让 left = mid + 1
  • 当 nums[mid] < nums[right]，则 min 可能是 mid 也可能在左半部分，所以让 right = mid
  • 当 nums[mid] = nums[right]，可能出现 0111 和 7111 这两种情况，此时让 right-1 总是正确的
    终止条件是 left=right，因此返回 nums[left] 即可。
1
2
3
4
5
6
7
8
9
10
11
12
def findMin(self, nums):
    left = 0
    right = len(nums)-1
    while left < right:
        mid = left + (right-left) // 2
        if nums[mid] == nums[right]:
            right -= 1
        elif nums[mid] < nums[right]:
            right = mid
        else:
            left = mid + 1
    return nums[left]

Find Peak Element

Leetcode : 162. Find Peak Element (Medium)

要求时间复杂度为 O(logn)，因此用二分查找。 当 nums[mid] < nums[mid+1] 时，峰值在 mid 右边。

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

Find the Duplicate Number

Leetcode : 287. Find the Duplicate Number (Medium)

问题描述：由题意，不能修改数组，即限制了不能对数组进行排序；要求空间复杂度为 o(1), 则不可以用字典实现；要求时间复杂度 < o(n2) 则不能暴力嵌套两次循环求解，想到只能有 o(nlogn) 的时间复杂度，则需要利用二分查找。

思路：按照抽屉原理，如果有 n+1 只袜子要放入 n 个抽屉中，那必定有至少一个抽屉中有至少两只袜子。

  1. 对于 1-n 中的数，必定有一个数出现了至少两次，我们可以先用二分查找选取 n/2
  2. 再遍历数组中小于等于 n/2 的数的个数 count，若 count > n/2 大，那么可以说明重复出现的数在 0-n/2 这个区间，否则在 n/2-n 这个区间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def findDuplicate(self, nums):
    low = 0
    high = len(nums) - 1
    while(low <= high):
        mid = low + (high-low) // 2
        count = 0
        for i in range(len(nums)):
            if nums[i] <= mid:
                count += 1
        if count > mid:
            high = mid - 1
        else:
            low = mid + 1
    return low

放置硬币

Leetcode : 441. Arranging Coins (Easy)

问题描述：1+2+…+x = n,则 x 为可以摆的层数，最后一层无法摆满时，不能计数。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def arrange_coins(n):
    if n < 0:
        return -1
    low = 0
    high = n
    while(low <= high):
        mid = low + (high-low)//2
        sum = mid * (1+mid) // 2
        if sum <= n and sum > n-mid:
            return mid
        elif sum > n:
            high = mid - 1
        else:
            low = mid + 1

有序数组的Single Element

Leetcode : 540. Single Element in a Sorted Array (Medium)

问题描述：

  1. 分三种情况，mid 刚好是 single；
  2. single 在左侧，mid 是奇数，则 mid 左右均有奇数个数，若 nums[mid]==nums[mid+1]，右侧还有两个数，single 在左侧；mid 是偶数，则mid 左右均有偶数个数，若 nums[mid]==nums[mid-1]，则 single 在左侧；
  3. single 在右侧。
  4. 时间复杂度为 o(logn)，典型算法有三个：二分查找，欧几里得算法（求最大公约数），幂运算
1
2
3
4
5
6
7
8
9
10
11
12
def single_element(nums):
    low = 0
    high = len(nums) - 1
    while(low < high): #1
        mid = low + (high-low)//2
        if(nums[mid] != nums[mid+1] and nums[mid]!= nums[mid-1]):
            return nums[mid]
        elif((mid%2 == 1 and nums[mid] == nums[mid+1]) or (mid%2 == 0 and nums[mid] == nums[mid-1])):
            high = mid -1
        else:
            low = mid + 1
    return nums[low]

备注：

  1. 此处不能等于，否则会出现数组越界情况，如 nums=[1,1,2] 时，此时是由于第一种情况是，判断 nums[mid] != nums[mid+1] 时，当 mid 为 len(nums) - 1 时会造成数组越界。