Modified Binary Search

Posted on

无处不在的二分思想。往往通过外部变量 track 中间结果，元素不是 distinct 时需要单独处理。有时仅为解法的一小步，bisect_left 第一个大于等于；bisect_right 第一个大于。

As we know, whenever we are given a sorted array or linked list or matrix, and we are asked to find a certain element, the best algorithm we can use is binary search.

This pattern describes an efficient way to handle all problems involving Binary Search. We will go through a set of problems that will help us build an understanding of this pattern so that we can apply this technique to other problems we might come across in the interviews.

Snippets

1
2
3
4
5
6
7
8
9
10
11
12
lo, hi = 0, len(nums) - 1
while lo <= hi:
    mid = lo + ((hi - lo) >> 1)
    if nums[mid] >= target:
        if mid == 0 or nums[mid-1] < target:  # find leftmost element
            return mid
        
        hi = mid - 1
    else:
        lo = mid + 1

return len(nums)  # all less

LeetCode

704. Binary Search
35. Search Insert Position
744. Find Smallest Letter Greater Than Target
34. Find First and Last Position of Element in Sorted Array
702. Search in a Sorted Array of Unknown Size
270. Closest Binary Search Tree Value
852. Peak Index in a Mountain Array
1095. Find in Mountain Array
33. Search in Rotated Sorted Array
153. Find Minimum in Rotated Sorted Array