Binary-Search

Posted on | In , |

https://blog.csdn.net/itsyarkee/article/details/6852338
http://www.cnblogs.com/grandyang/p/6854825.html
https://leetcode.com/problems/minimize-max-distance-to-gas-station/description/
https://www.jianshu.com/p/de025ad0d6b5

  • consider inital boundary, exit case (<, <=, diff<1e-6), and int v.s. float
  1. Standard Version (go through all elements of the list if not found)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    l, r = 0, len(nums)-1
    while l<=r:
        m = l + (l - r)/2
        if nums[m] > target:
            r = m - 1
        elif nums[m] < target:
            l = m + 1
        else:
            return m
        return "Not Found"

https://github.com/Frees0u1/ClassicalCode/blob/master/301_BinarySearch.cpp

  1. find the first satisfied index (lower bound)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    #  lower小于, upper小等
    # 找到nums[l, r)大于等于key值的第一个元素位置 [左闭-右开)
    l, r = 0, len(nums)
    while l < r:
        m = l + (r - l)/2
        if nums[m] < target:
            l = m + 1
        else: # nums[m] >= target
            r = m
    return l if nums[l] == target else None

  2. find the first satisfied index that greater than target (upper bound 1)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    #  lower小于, upper小等
    # 找到严格大于key值的第一个元素
    l, r = 0, len(nums)
    while l < r:
        m = l + (r - l)/2
        if nums[m] <= target:
            l = m + 1
        else:
            r = m
    return l if l < len(nums) and nums[l] > target else None

  3. find the last satisfied index (upper bound 2)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    #  lower小于, upper小等
    # 找到严格大于key值的第一个元素
    l, r = 0, len(nums)
    while l < r:
        m = l + (r - l)/2
        if nums[m] <= target:
            l = m + 1
        else:
            r = m
    return l-1 if 0<=l-1 < len(nums) and nums[l-1] == target else None

or

1
2
3
4
5
6
7
8
l, r = 0, len(nums)-1
while l < r:
    m = l + (r - l)/2
    if nums[m] <= target:
        l = m 
    else:
        r = m - 1 
return l

  1. float binary search
    1
    2
    3
    4
    5
    6
    7
    8
    l, r = min(A), max(A)
    while r - l > 0.00001:
        m = (r+l) /2.0
        if possible(m):
            l = m
        else:
            r = m
    return l
  • n m matrix convert to an array => matrix[x][y] => a[x m + y]
  • an array convert to n * m matrix => a[x] =>matrix[x / m][x % m];

Binary Modifications

  • acceleration
    1
    2
    3
    4
    5
    6
    7
    8
    9
    # https://leetcode.com/problems/divide-two-integers/description/
    while dividend >= divisor:
        i, tmp = 1, divisor
        while dividend >= divisor:
            dividend -= divisor
            res += i
            divisor <<= 1
            i <<= 1
        divisor = tmp

Intervals

  • sort by (start, -end)
  • find and merge, use binary search to accelerate

https://www.hrwhisper.me/leetcode-intervals/

Interval Fundamentals

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
# time O(N log(N)) Space O(1)
def mergeInterval(intervals):
    intervals.sort(key=lambda a: a.start)
    ans = []
    for t in intervals:
        if not ans or ans[-1].end < t.start:
            ans.append(t)
        else:
            # if there is an overlap, expand the previous interval's right end
            ans[-1].end = max(ans[-1].end, t.end)
    return ans
# time O(N) space O(1)
def insertInterval(intervals, newInterval):
    def binary_search(a, x):
        l, r = 0, len(a)
        while l < r:
            m = l + (r-l) /2
            # use <= to get last satisfied index
            if a[m].start <= x.start:
                l = m +1
            else:
                r = m
        return l
    
    index = binary_search(intervals, newInterval)
    res = intervals[:index]
    if res and newInterval.start <= res[-1].end:
        res[-1].end = max(res[-1].end, newInterval.end)
    else:
        res.append(newInterval)
    
    # same as merge interval code
    for i in range(index, len(intervals)):
        if intervals[i].start <= res[-1].end:
            res[-1].end = max(res[-1].end, intervals[i].end)
        else:
            res.append(intervals[i])
    return res

Meeting rooms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# Time O(N*K) Space O(K)
def minMeetingRooms(intervals):
    intervals.sort(key=lambda x:(x.start,-x.end))
    heap = []
    res = 0
    for i in range(len(intervals)):
        if not heap:
            heapq.heappush(heap, intervals[i].end)
        else:
            while heap and heap[0] <= intervals[i].start:
                heapq.heappop(heap)
            heapq.heappush(heap, intervals[i].end)
        res = max(res, len(heap))
    return res