Algorithm - Binary Search (1)

Classic binary search scenarios are find a number, and find boundaries.
Leetcode Binary Search Problem Set (1) - Medium

• 278.First Bad Version
• 33.Search in Rotated Sorted Array
• 1283.Find the Smallest Divisor Given a Threshold
• 875.Koko Eating Bananas
• 1011.Capacity To Ship Packages Within D Days
• 981.Time Based Key-Value Store

Template

def binary_search(nums, target):
    left = 0
    right = ...
    while ...:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            ...
        elif nums[mid] < target:
            left = ...
        elif nums[mid] > target:
            right = ...
    return ...

• Using elif instead of else in binary search can show more details, which is better for beginner to debug.
• left + (right - left) / 2 is the same as (right + left) / 2, is avoiding int overflow. Python int won’t overflow though.

Find a number

Search interval [left, right], left == right + 1 is the terminal criteria, which is an empty interval.

def binary_search(nums, target):

    left = 0
    right = len(nums) - 1  # the last element

    while left <= right:

        mid = left + (right - left) // 2

        if nums[mid] == target:
            return mid

        # search[mid + 1, right]
        elif nums[mid] < target:
            left = mid + 1

        # search [left, mid - 1]
        elif nums[mid] > target:
            right = mid - 1

Find Left Boundary

Search [left, right)

def find_left_bound(nums, target):
    left = 0
    right = len(nums)

    while left < right:

        mid = left + (right - left) // 2

        if nums[mid] == target:
            right = mid

        elif nums[mid] < target:
            left = mid + 1

        elif nums[mid] > target:
            right = mid

    return left

Shrink right bound to get the

Find Right Boundary

def find_right_bound(nums, target):
    if len(nums) == 0:
        return -1

    left = 0
    right = len(nums)

    while left < right:

        mid = left + (right - left) // 2

        if nums[mid] == target:
            left = mid + 1

        elif nums[mid] < target:
            left = mid + 1

        elif nums[mid] > target:
            right = mid

    return left - 1

278. First Bad Version

Finding the left bound of bad version interval
[G, G, G, G, G, G, G, B, B, B] => serch => [B, B, B]

The left pointer should point to the first bad version.

def firstBadVersion(self, n):
    """
    :type n: int
    :rtype: int
    """
    left = 1
    right = n
    while left < right:
        mid = left + (right - left) // 2
        
        if not isBadVersion(mid):
            left = mid + 1
        else:
            right = mid
    return left

33. Search in Rotated Sorted Array

Use binary search 2 times:

1. find pivot (actually is find left bound)
2. find target number.

def search(self, nums: List[int], target: int) -> int:
    left = 0
    right = len(nums) - 1
    
    if nums[left] > nums[right]:
        # search pivot in [left, right)
        while left < right:
            mid = (left + right) // 2
            if nums[mid] > nums[right]:
                left = mid + 1
            else:
                right = mid

        p = left
        # search left
        if target >= nums[0]:
            left = 0
            right = p - 1
        # search right
        else:
            left = p
            right = 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

1283. Find the Smallest Divisor Given a Threshold

divisor range: [1, max(nums)]

from math import ceil
def smallestDivisor(self, nums: List[int], threshold: int) -> int:
    lo = 1
    hi = max(nums)
    
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if sum([ceil(n / mid) for n in nums]) > threshold:
            # divisor too small
            lo = mid + 1
        else:
            hi = mid
    
    return lo

875. Koko Eating Bananas

Typical find a number problem.
When jump out of the loop, left == right + 1, is the max number KOKO should eat.

from math import ceil
def minEatingSpeed(self, piles: List[int], H: int) -> int:
    left = 1
    right = max(piles)  # 1 pile / h
    
    while left <= right:
        mid = left + (right - left) // 2
        cur = sum([ceil(p / mid) for p in piles])
        if cur == H:
            return mid
        elif cur > H:
            # need less time, eat more banana each time
            left = mid + 1
        else:
            right = mid - 1
    # left == right + 1
    return left

1011. Capacity To Ship Packages Within D Days

Left bound: max -> as least can move the heaviest item
Right bound: sum -> move all in one day

def shipWithinDays(self, weights: List[int], D: int) -> int:
        
    def get_min_days(weights, cap):
        day, cur = 1, 0
        for w in weights:
            if cur + w > cap:
                day += 1
                cur = 0
            cur += w
        return day   
    
    left = max(weights)
    right = sum(weights)
    while left <= right:
        mid = left + (right - left) // 2
        day = get_min_days(weights, mid)
        if day > D:
            left = mid + 1  # load more each day
        else:
            right = mid - 1
    return left

981. Time Based Key-Value Store

class TimeMap:
    
    from collections import defaultdict
    def __init__(self):
        self.keymap = defaultdict(list)
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.keymap[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.keymap:
            return None
        
        values = self.keymap[key]
        if timestamp < values[0][0]:
            return ''
        if timestamp >= values[-1][0]:
            return values[-1][1]
        
        # find right bound
        left = 0
        right = len(values)
        while left < right:
            mid = (left + right) // 2
            stamp, value = values[mid]
            if stamp == timestamp:
                return value
            elif stamp < timestamp:
                left = mid + 1
            else:
                right = mid
        return values[left - 1][1]