binary_search.md

binary_search

binary_search.binary_search(lo, hi, function)

Find the first index i where lo <= i <= hi that satisfies function.

Median of Two Sorted Arrays

def findMedianSortedArrays(nums1, nums2):

    def median(a, b, extrema):
        k = -1 * (extrema == max)
        half = []
        if a:
            half += [nums2[j + k]]
        if b:
            half += [nums1[i + k]]
        return extrema(half)

    nums1, nums2 = sorted([nums1, nums2], key=len)
    m, n = len(nums1), len(nums2)
    sum_len = m + n
    mean_len = (sum_len + 1)//2
    i = binary_search(0, m,
        lambda x: x and nums1[x - 1] > nums2[mean_len - x]
    )
    j = sum_len - i
    return median_low if sum_len%2 else (median_low
        + median(i == m, j == n, min)
    )/2

Search in Rotated Sorted Array

def search(nums, target):
    if nums:
        n = len(nums)
        m = n - 1
        i = binary_search(0, m, lambda x: nums[x - 1] > nums[x])
        j = binary_search(i, i + m, lambda y: nums[y%n] == target)%n
        return j if nums[j] == target else -1
    return -1

Find First and Last Position of Element in Sorted Array

def searchRange(nums, target):
    if nums:
        n = len(nums) - 1
        i = binary_search(0, n - 1, lambda x: nums[x] >= target)
        if nums[i] == target:
            j = binary_search(i, n, lambda y: nums[y] > target) - 1
            return [i, j]
        else:
            return [-1, -1]
    return [-1, -1]

Search a 2D Matrix

def searchMatrix(matrix, target):
    m = len(matrix[0])
    i = binary_search(0, len(matrix)*m - 1,
        lambda x: matrix[x//m][x%m] >= target
    )
    return matrix[i//m][i%m] == target

Search in Rotated Sorted Array II

def search(nums, target):
    if nums:
        n = len(nums)
        m = n - 1
        lo, hi = 0, m
        while lo < n and nums[lo] == nums[0]:
            lo += 1
        while hi and nums[hi] == nums[-1]:
            hi -= 1
        i = binary_search(lo, hi, lambda x: nums[x - 1] > nums[x])
        return nums[binary_search(i, i + m,
            lambda y: nums[y%n] >= target
        )%n] == target
    return False

Find Minimum in Rotated Sorted Array

def findMin(nums):
    return nums[binary_search(0, len(nums) - 1,
        lambda x: nums[x - 1] > nums[x]
    )]

Find Peak Element

def findPeakElement(nums):
    n = len(nums)
    if n > 2:
        i = binary_search(1, n - 2,
            lambda x: nums[x - 1] < nums[x] > nums[x + 1]
        )
        return nums[i]
    else:
        return max(nums)

H-Index II

def hIndex(citations):
    n = len(citations)
    return binary_search(0, n - 1, lambda x: citations[x] >= n - x)

Longest Increasing Subsequence

def lengthOfLIS(nums):
    tails, size = [0]*len(nums), 0
    for num in nums:
        i = binary_search(0, size, lambda x: tails[x] >= num)
        tails[i], size = num, max(i + 1, size)
    return size

Valid Perfect Square

def isPerfectSquare(num):
    return binary_search(1, num, lambda x: x**2 >= num)**2 == num

Split Array Largest Sum

def splitArray(nums, m):

    def is_valid(target):
        subarray_sum = counter = 0
        for num in nums:
            subarray_sum += num
            if subarray_sum > target:
                subarray_sum = num
                counter += 1
                if counter >= m: return False
        return True

    array_sum = sum(nums)
    return binary_search(max(nums), is_valid(array_sum)
    ) if m > 1 else array_sum

Koko Eating Bananas

def minEatingSpeed(piles, H):

    def can_eat(K):
        hours = 0
        for pile in piles:
            hours += pile//K
            if pile%K:
                hours += 1
        return hours <= H

    return binary_search(1, max(piles), can_eat)

Find Positive Integer Solution for a Given Equation

def findSolution(customfunction, z):
    lo, hi = 1, 1001
    pairs = []
    for x in range(1, 1001):
        if not customfunction.f(x, lo) < customfunction.f(x, hi) < z:
            y = binary_search(lo, hi, lambda b: customfunction.f(x, b) >= z)
            value = customfunction.f(x, y)
            if value >= z:
                if value == z: pairs += [[x, y]]
                hi = y
            else:
                lo = y
    return pairs

Find the Smallest Divisor Given a Threshold

def smallestDivisor(nums, threshold):
    return binary_search(1, max(nums),
        lambda x: sum((i + x - 1)//x for i in nums) <= threshold
    )