Binary Search

Algorithms
binary search
Catalogue
  1. 1. 经典二分查找
    1. 1.1. LintCode 457. Classical Binary Search
    2. 1.2. 74. Search a 2D Matrix
    3. 1.3. 九章算法二分查找模板
  2. 2. 边界系列
    1. 2.1. 278. First Bad Version
    2. 2.2. 35. Search Insert Position
    3. 2.3. 34. Search for a Range
  3. 3. 旋转数组系列
    1. 3.1. 162. Find Peak Element
    2. 3.2. 153. Find Minimum in Rotated Sorted Array
    3. 3.3. 154. Find Minimum in Rotated Sorted Array II
    4. 3.4. 33. Search in Rotated Sorted Array
    5. 3.5. 81. Search in Rotated Sorted Array II
  4. 4. 数值二分型
    1. 4.1. 374. Guess Number Higher or Lower
    2. 4.2. 367. Valid Perfect Square
    3. 4.3. 69. Sqrt(x)

Given a sorted array of n elements, write a function to search a given element x in array.

  • Search算法里的入门算法，其实很多高级算法的思路都是以二分查找为基本思想引出的，特别是那些和logn相关的算法，比如说自平衡二叉树

经典二分查找

  • 有序, 数组
  • Why 链表不可以？Why 无序不可以？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def findPosition(self, nums, target):
        if not nums:
            return -1

        # 1 Two Pointers 指向可行解的范围
        start, end = 0, len(nums)-1

        while start <= end:
            # 2 Median Index
            mid = start + (end - start) // 2

            # 3 Check Median Index Val
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                end = mid - 1   # Adjust end
            else:
                start = mid + 1 # Adjust start
        return -1

74. Search a 2D Matrix

  • 一维Array和二维Matrix的转换
    • index => (x, y)
    • x = index / col
    • y = index % col
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def searchMatrix(self, matrix, target):
        if not matrix:
            return False
        m, n = len(matrix), len(matrix[0])
        start, end = 0, m*n-1
        while start <= end:
            mid = start + (end - start) / 2
            row, col = mid / n, mid % n
            if matrix[row][col] < target:
                start = mid + 1
            elif matrix[row][col] > target:
                end = mid - 1
            else:
                return True
        return False

九章算法二分查找模板

  • while 循环 ?
    • while start + 1 < end, 留两个值做post processing
    • while start < end, 留一个值做post processing
    • while start < = end, 不留值
  • 缩小查找范围 ?
    • start = mid 还是 start = mid + 1
    • end = mid 还是 end = mid + 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def findPosition(self, A, target):
    if(len(A) == 0):
        return -1

    start = 0
    end = len(A) - 1

    while(start + 1 < end):
        mid = start + (end - start) / 2
        if(A[mid] == target):
            return mid
        if(A[mid] < target):
            start = mid
        else:
            end = mid

    #post processing
    if (A[start] == target):
        return start
    elif (A[end] == target):
        return end
    else:
        return -1
  • Double Check 小技巧:
    • 当前这个mid对应的值是不是 可能是要找的结果，mid + 1 还是 mid ?
    • start = mid 一定要用 while start + 1 < end !!!
    • 要找的结果是不是一定在数组当中！start < end 还是 start < = end

边界系列

  • Input是标准的 Sorted Array（单调增或者单调减）
    • First or Last of Occrance!
    • 大于等于，小于等于，大于，小于，等于
  • 每次淘汰的空间要确定是不属于结果范围的！

278. First Bad Version

  • 000000011111111
  • Find The First Occrance of an Element
    • 找的元素在不在数组里？while start < end 还是 while start < = end
    • How about Last Good Version?
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
# 写法1. 这种写法条件是target存在，且start = mid + 1
class Solution(object):
    def firstBadVersion(self, n):
        start, end = 1, n
        while start < end:
            mid = start + (end - start) / 2
            ret = isBadVersion(mid)
            if ret:
                end = mid
            else:
                start = mid + 1
        return start

# 写法2. 九章算法模板 - 预留两位做post processing
class Solution(object):
    def firstBadVersion(self, n):
        start, end = 1, n

        # 预留两位最后处理
        while start + 1 < end:
            mid = start + (end - start) / 2
            ret = isBadVersion(mid)
            if ret:
                end = mid
            else:
                start = mid + 1

        # Post Processing
        if isBadVersion(start):
            return start
        else:
            return end

35. Search Insert Position

  • 找 > = target 的 first occrence
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def searchInsert(self, nums, target):
        if not nums:
            return 0
        if target > nums[-1]:
            return len(nums)

        start, end = 0, len(nums)-1
        while start + 1 < end:
            mid = start + (end - start) / 2
            if nums[mid] >= target:
                end = mid
            else:
                start = mid + 1

        # Post Precessing
        if nums[start] >= target:
            return start
        else:
            return end

34. Search for a Range

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
class Solution(object):
    def searchRange(self, nums, target):
        if not nums:
            return [-1, -1]

        # First Occurance
        start, end = 0 , len(nums) - 1
        while start + 1 < end:
            mid = start + (end - start) / 2
            if nums[mid] >= target:
                end = mid
            else:
                start = mid + 1

        if nums[start] == target:
            first = start
        elif nums[end] == target:
            first = end
        else:
            return [-1, -1]

        # Last Occurance
        start, end = 0, len(nums) - 1
        while start + 1 < end:
            mid = start + (end - start) / 2
            if nums[mid] <= target:
                start = mid
            else:
                end = mid - 1

        if nums[end] == target:
            return [first, end]
        else:
            return [first, start]

旋转数组系列

  • 只有Sorted Array才能做Binary Search？
    • Input数组不再是单调递增或者单调递减
  • 每次淘汰的空间要确定是不属于结果范围的！

162. Find Peak Element

  • 根据要找的Target条件缩小Search的范围！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 模版解法
class Solution(object):
    def findPeakElement(self, nums):
        if len(nums) <= 1: return 0

        start, end = 0 , len(nums)-1
        while start + 1 < end:
            mid = start + (end - start) / 2
            if nums[mid] < nums[mid+1]:
                start = mid + 1
            else:
                end = mid

        if nums[start] > nums[end]:
            return start
        else:
            return end
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def findPeakElement(self, nums):
        if len(nums) <= 1: return 0

        start, end = 0 , len(nums)-1
        while start < end:
            mid = start + (end - start) / 2
            if nums[mid] < nums[mid+1]:
                start = mid + 1
            else:
                end = mid

        return start

153. Find Minimum in Rotated Sorted Array

  • Why nums[mid] 和 nums[end]比较？
1
2
3
4
5
6
7
8
9
10
11
# 模版解法
class Solution(object):
    def findMin(self, nums):
        start, end = 0, len(nums)-1
        while start + 1 < end:
            mid = start + (end - start) / 2
            if nums[mid] > nums[end]:
                start = mid + 1
            else:
                end = mid
        return min(nums[start], nums[end])
1
2
3
4
5
6
7
8
9
10
class Solution(object):
    def findMin(self, nums):
        start, end = 0, len(nums)-1
        while start < end:
            mid = start + (end - start) / 2
            if nums[mid] > nums[end]:
                start = mid + 1
            else:
                end = mid
        return nums[start]

154. Find Minimum in Rotated Sorted Array II

  • What if duplicates are allowed?
  • Worst Case O(n)
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
# nums[mid] == nums[end] ?
class Solution(object):
    def findMin(self, nums):
        start, end = 0, len(nums)-1
        while start < end:
            mid = start + (end - start) / 2
            if nums[mid] < nums[end]:
                end = mid
            elif nums[mid] > nums[end]:
                start = mid + 1
            else:
                end -= 1
        return nums[start]

# 套模板
class Solution(object):
    def findMin(self, nums):
        start, end = 0, len(nums)-1
        while start + 1 < end:
            mid = start + (end - start) / 2
            if nums[mid] < nums[end]:
                end = mid
            elif nums[mid] > nums[end]:
                start = mid + 1
            else:
                end -= 1
        return min(nums[start], nums[end])

33. Search in Rotated Sorted Array

  • 1 把Array先根据nums[end]分成在前段还是后段
  • 2 再根据nums[mid]的大小
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def search(self, nums, target):
        start, end = 0, len(nums)-1
        while start <= end:
            mid = start + (end - start) / 2
            if nums[mid] == target:
                return mid
            # 前还是后，根据 num[end] 根据nums[start]也行
            if nums[mid] <= nums[end]:
                if nums[mid] < target <= nums[end]:
                    start = mid + 1
                else:
                    end = mid - 1
            else:
                if nums[start] <= target < nums[mid]:
                    end = mid - 1
                else:
                    start = mid + 1
        return -1

81. Search in Rotated Sorted Array II

  • nums may contain duplicates
  • nums[mid] == nums[start] 或者 nums[mid] == nums[end]的时候无法判断nums[mid]是在前段还是后段！
    • start += 1 缩减范围, Worst Case : O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def search(self, nums, target):
        start, end = 0, len(nums)-1
        while start <= end:
            mid = (start + end) / 2
            if nums[mid] == target:
                return True

            if nums[mid] < nums[start]:
                if nums[mid] < target <= nums[end]:
                    start = mid + 1
                else:
                    end = mid - 1
            elif nums[mid] > nums[start]:
                if nums[start] <= target < nums[mid]:
                    end = mid - 1
                else:
                    start = mid + 1
            else:
                start += 1
        return False

数值二分型

  • 典型的二分法: 输入是数组，双指针分别是数组的index
  • Input不再是Array，不再以index，而是以value来做二分

374. Guess Number Higher or Lower

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def guessNumber(self, n):
        start, end = 1, n
        while start < end:
            mid = start + (end - start) // 2
            ret = guess(mid)
            if ret == 0:
                return mid
            elif ret < 0:
                end = mid - 1
            else:
                start = mid + 1
        return start

367. Valid Perfect Square

  • ret = mid * mid 来判断范围
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def isPerfectSquare(self, num):
        start, end = 1, num
        while start <= end:
            mid = start + (end - start) / 2
            ret = mid * mid
            if ret > num:
                end = mid - 1
            elif ret < num:
                start = mid + 1
            else:
                return True
        return False

69. Sqrt(x)

  • 在0～x中找最大的数r，满足r * r < = x
  • Why start + 1 < end ?
  • 剩余的搜索范围都是满足搜索条件的！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def mySqrt(self, x):
        start, end = 0, x
        while start + 1 < end:
            mid = start + (end - start) / 2
            ret = mid * mid
            if ret > x:
                end = mid - 1
            elif ret < x:
                start = mid
            else:
                return mid

        if end * end <= x:
            return end
        else:
            return start
Share