二分查找基础

二分查找(力扣704)

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

x的平方根(力扣69)

思路：使用二分的思路，对x每次都折半对比，最终会得到left > right的点，将right返回，或将left+1返回

我们以8举例,left,right和mid的变化如下：

边界 第一次 第二次 第三次 第四次 第五次
mid 4（right=mid-1） 1(left=mid+1) 2(left=mid+1) 3(right=mid-1) 2(return right)
left 0 0 2 3 3
right 8 3 3 3 2 
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def mySqrt(self, x: int) -> int:
        left, right = 0, x
        while left <= right:
            mid = left + (right -left)//2
            if mid*mid == x:
                return mid
            elif mid*mid < x:
                left = mid + 1
            else:
                right = mid -1
        return right

搜索二维矩阵（力扣74）

思路：将矩阵拉平之后就是一个基本的二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        temp = [j for i in matrix for j in i]
        return self.binear_search(temp, target)
        
    def binear_search(self, nums, target):
        left, right = 0, len(nums)-1
        while left <= right:
            mid = (left + right)//2
            if nums[mid] == target:
                return True
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return False

空间复杂度为1的算法思路:

这里最重要的是要记住一点，拉平之后的索引在原矩阵中的位置为：

row = idx // n col = idx % n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix or not matrix[0]: return False
        m = len(matrix)
        n = len(matrix[0])
        left, right = 0, m*n-1
        while left <= right:
            mid = (left + right) // 2
            value = matrix[mid//n][mid%n]
            if value == target:
                return True
            elif value > target:
                right = mid - 1
            else:
                left = mid + 1
        return False