记录二分查找思想相关题目的解题。

0. 思路

二分查找 难就难在，arr[mid]跟谁比.

我们的目的是：当进行一次比较时，一定能够确定答案在mid的某一侧。

一般的比较原则有：

如果有目标值target，那么直接让arr[mid] 和 target 比较即可。

如果没有目标值target，一般可以考虑 端点 。

1. 题目描述 - 华为 - 二维数组的查找

Question source

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

解题思路

假设arr数组，val，tar如下图所示：

如果我们把二分值定在右上角或者左下角，就可以进行二分。这里以右上角为例，左下角可自行分析：

图片说明：

1）设初始值为右上角元素，arr[0][5] = val，目标tar = arr[3][1]

2）接下来进行二分操作：

3）如果val == target,直接返回

4）如果 tar > val, 说明target在更大的位置，val左边的元素显然都是 < val，间接 < tar，说明第 0 行都是无效的，所以val下移到arr[1][5]

5）如果 tar < val, 说明target在更小的位置，val下边的元素显然都是 > val，间接 > tar，说明第 5 列都是无效的，所以val左移到arr[0][4]

6）继续步骤2）

Complexity

  • 时间复杂度：O(m+n) ，其中m为行数，n为列数，最坏情况下，需要遍历m+n次。
  • 空间复杂度：O(1)

Code

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        row,column = 0, len(matrix[0]) - 1 

        while row <= len(matrix)-1 and column >= 0: 
            if matrix[row][column] > target:
                column -= 1
            elif matrix[row][column] < target:
                row += 1
            elif matrix[row][column] == target:
                return True
        return False

2. 题目描述 - 剑指OFFER - 旋转数组的最小数

Question source

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

解题思路

这里我们把 0. 思路 中提到的 target 看作是右端点，因为此题的右端点是一个拐点，与mid对比，有助于寻找最小值。

mid = low + (high - low)/2

需要考虑三种情况：

(1)array[mid] > array[high]:

出现这种情况的array类似[3,4,5,6,0,1,2]，此时最小数字一定在mid的右边。

low = mid + 1

(2)array[mid] == array[high]:

出现这种情况的array类似 [1,0,1,1,1] 或者[1,1,1,0,1]，此时最小数字不好判断在mid左边，还是右边,这时只好一个一个试

high = high - 1

(3)array[mid] < array[high]:

出现这种情况的array类似[2,2,3,4,5,6,6],此时最小数字一定就是array[mid]或者在mid的左边。因为右边必然都是递增的。

high = mid

注意这里有个坑：如果待查询的范围最后只剩两个数，那么mid 一定会指向下标靠前的数字。比如 array = [4,6]，array[low] = 4 ，array[mid] = 4 ，array[high] = 6 ;

如果high = mid - 1，就会产生错误， 因此high = mid

但情形(1)中low = mid + 1就不会错误

Complexity

  • 时间复杂度：二分，所以为O(longN)， 但是如果是[1, 1, 1, 1],会退化到O(n)
  • 空间复杂度：没有开辟额外空间，为O(1)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if len(rotateArray)==0:
            return 0
        low,high = 0,len(rotateArray)-1
        while(low<high):
            mid = (low + high)//2
            if rotateArray[mid] < rotateArray[high]:
                high = mid # 注意不能写 high = mid - 1，最小数字可能是array[mid]，mid-1会完全漏掉正确解
            elif rotateArray[mid] > rotateArray[high]:
                low = mid + 1
            else:
                high = high - 1
        return rotateArray[low] # 注意不能写 rotateArray[mid]

3. 题目描述 - 剑指OFFER - 数字在排序数组中出现的次数

Question source

题目抽象：给定一个非递减排序的数组nums和一个目标值target，查找target出现的次数。

解题思路

暴力方法的时间复杂度为O（n），并且没有用到升序条件。

可以用二分法。因为有序，所以目标值target如果有多个，肯定是连在一起。又已知我们可以在有序数组中查找任意一个值，因此我们可以先查找目标范围的下界和上界。

下界first定义为：如果存在目标值，则指向第一个目标值，否则，如果不存在，则指向-1。

上界last定义为：如果存在目标值，则指向大于目标值的第一个值，否则，如果不存在，则指向-1。

Complexity

  • 时间复杂度：二分，所以为O(longN)， 但是如果是[1, 1, 1, 1],会退化到O(n)
  • 空间复杂度：没有开辟额外空间，为O(1)

Code

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
44
45
46
47
48
# -*- coding:utf-8 -*-
class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        num=0
        if data:
            first = self.getFirst(data,k)
            print(first)
            last = self.getLast(data,k)
            print(last)
            if(first > -1 and last > -1):
                num = last - first
                return num
        return num
    
    def getFirst(self, data, k):
        l,r=0,len(data)-1
        while l<=r:
            if data[l] == k: return l # 不要漏掉，否则缺少对首位为下边届的判断，会造成数组下标溢出
            mid = (l+r)//2
            if data[mid]>k or (data[mid]==k and data[int(mid-1)]==k):
                r=mid-1
                print(l,r)
            elif data[mid]<k :
                l=mid+1
                print(l,r)
            elif data[mid]==k and data[int(mid-1)]!=k:
                 
                print(l,r)
                return mid
                 
        return -l
         
    def getLast(self, data, k):   
        l,r=0,len(data)-1
        while l<=r:
            if data[r] == k: return r+1 # 不要漏掉，否则缺少对末尾位为上边届的判断，会造成数组下标溢出
            mid = (l+r)//2
            if data[mid]>k :
                r=mid-1
#                 print(l,r)
            elif data[mid]<k or (data[mid]==k and data[int(mid+1)]==k):
                l=mid+1
#                 print(l,r)
            elif data[mid]==k and data[int(mid+1)]!=k:
                 
                return mid+1
        return -1

相关题目

[1 ]LeetCode 33