[Leetcode] Binary Search

Posted on | In , |

Binary Search In Array

Great variants: https://www.geeksforgeeks.org/variants-of-binary-search/

https://leetcode-cn.com/problems/binary-search/solution/er-fen-cha-zhao-de-xun-huan-bu-bian-liang-zhi-yao-/

  • r = len(nums) or r = len(nums) - 1: r = len(nums) 左闭右开，在最后的循环中r是不被包括在循环以内的。因此用 while l < r 做循环条件，以 l = r 结束。 r的移动规则为 r = m， 因为下一次应该查找右边界为m的前一个元素。[l, m - 1]， 因为r指向最后一个元素的后一个元素， 当r = m， 下次查找范围就为 [l, r) => [l, m - 1].
  • r = len(nums) - 1: 左闭右闭区间。循环条件为 while l <= r, 当l < r 时，会忽略最后一个r元素。r的移动规则为r = m - 1,

Variant 1: Contains (True or False)

1
2
3
4
5
6
7
8
9
10
11
12
13
arr = [2, 3, 3, 5, 5, 5, 6, 6]

def contains(arr, target):
    l, r = 0, len(arr) - 1
    while l <= r:
        mid = (l + r) // 2
        if arr[mid] < target:
            l = mid + 1
        elif arr[mid] > target:
            r = mid - 1
        else:
            return True
    return False

Variant 2 First occurrence index of target

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def firstOccur(arr, target):
    l, r = 0, len(arr) - 1
    ans = -1
    while l <= r:
        mid = (l + r) // 2
        if arr[mid] < target:
            l = mid + 1
        elif arr[mid] > target:
            r = mid - 1
        else:
            ans = mid
            # look for the occurance before mid
            r = mid - 1
    return ans

Variant 3 Last occurrence index of target

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def lastOccur(arr, target):
    l, r = 0, len(arr) - 1
    ans = -1
    while l <= r:
        mid = (l + r) // 2
        if arr[mid] > target:
            r = mid - 1
        elif arr[mid] < target:
            l = mid + 1
        else:
            ans = mid
            # look for the occurance after mid
            l = mid + 1
    return ans

Variant 4 Find first occurance of the smallest element greater than target

1
2
3
4
5
6
7
8
9
10
11
def smallestGreater(arr, target):
    l, r = 0, len(arr) - 1
    ans = -1
    while l <= r:
        mid =  (l + r) // 2
        if arr[mid] > target:
            ans = mid
            r = mid - 1
        else:
            l = mid + 1
    return ans

Variant 5 Find the last occurance of the greatest element that’s smaller than target

1
2
3
4
5
6
7
8
9
10
def greatestSmaller(arr, target):
    l, r = 0, len(arr) - 1
    ans = -1
    while l <= r:
        mid = (l + r) // 2
        if target > arr[mid]:
            ans = mid
            l = mid + 1
        else:
            r = mid - 1

Template: https://leetcode.com/problems/split-array-largest-sum/discuss/769701/Python-Clear-explanation-Powerful-Ultimate-Binary-Search-Template.-Solved-many-problems.

1
2
3
4
5
6
7
8
9
10
11
12
def binary_search(array) -> int:
    def condition(value) -> bool:
        pass

    left, right = 0, len(array)
    while left < right: # left < right - 1
        mid = left + (right - left) // 2
        if condition(mid):
            right = mid
        else:
            left = mid + 1 # left = mid
    return left
  • Correctly initialize the boundary variables left and right. Only one rule: set up the boundary to include all possible elements;
  • Decide return value. Is it return left or return left - 1? Remember this: after exiting the while loop, left is the minimal k​ satisfying the condition function;
  • Design the condition function.

410. Split Array Largest Sum

Leetcode: https://leetcode.com/problems/split-array-largest-sum/

Given a candidate C(minimal largest sum), compute the number groups k needed.
(Greedy partition): https://www.youtube.com/watch?v=_k-Jb4b7b_0 after 12:00

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def splitArray(self, nums: List[int], m: int) -> int:
    def needGroup(maxSum): # return number of groups so that the sum of every group is smaller than maxSum
        _sum = 0
        i = 0
        k = 1
        while i < len(nums):
            _sum += nums[i]
            if _sum > maxSum:
                _sum = 0
                i -= 1
                k += 1
            i += 1
        return k > m
    left, right = max(nums), sum(nums) + 1
    while left < right:
        mid = left + (right - left) // 2
        if needGroup(mid):
            # proposed sum is too small
            left = mid + 1
        else:
            right = mid
    return left

683. K Empty Slots

Leetcode: https://leetcode.com/problems/k-empty-slots/description/

Video: https://www.youtube.com/watch?v=K8Nk0AiIX4s

74. Search a 2D Matrix

Binary search directly in 2D array, and use pivot to find the correct position in matrix.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
    l = 0
    if not matrix or not matrix[0]:
        return False
    
    r = len(matrix) * len(matrix[0]) - 1
    n = len(matrix[0])
    while l <= r:
        mid = (l + r) // 2
        row = mid // n
        col = mid % n
        if row >= len(matrix) or col >= len(matrix[0]):
            return False
        if matrix[row][col] < target:
            l = mid + 1
        elif matrix[row][col] > target:
            r = mid - 1
        else:
            return True
    return False

240. Search a 2D Matrix II

Leetcode: https://leetcode.com/problems/search-a-2d-matrix-ii/

1
2
3
4
5
6
7
8
9
10
11
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
    col = 0
    row = len(matrixÎ) - 1
    while col >= 0 and col < len(matrix[0]) and row >= 0 and row < len(matrix):
        if matrix[row][col] < target:
            col += 1
        elif matrix[row][col] > target:
            row -= 1
        else:
            return True
    return False

378. Kth Smallest Element in a Sorted Matrix

Leetcode: https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/

We want to count the number of elements in the left half of the number range of which we know the middle element and the two extremes as well.

An alternate could be to apply the Binary Search on the “number range” instead of the “index range”. As we know that the smallest number of our matrix is at the top left corner and the biggest number is at the bottom lower corner. These two number can represent the “range” i.e., the start and the end for the Binary Search. Here is how our algorithm will work:

  1. Start the Binary Search with start = matrix[0][0] and end = matrix[n-1][n-1].
  2. Find middle of the start and the end. This middle number is NOT necessarily an element in the matrix.
  3. Count all the numbers smaller than or equal to middle in the matrix. As the matrix is sorted, we can do this in O(N).
  4. While counting, we can keep track of the “smallest number greater than the middle” (let’s call it n1) and at the same time the “biggest number less than or equal to the middle” (let’s call it n2). These two numbers will be used to adjust the “number range” for the Binary Search in the next iteration.
  5. If the count is equal to ‘K’, n1 will be our required number as it is the “biggest number less than or equal to the middle”, and is definitely present in the matrix.
  6. If the count is less than ‘K’, we can update start = n2 to search in the higher part of the matrix and if the count is greater than ‘K’, we can update end = n1 to search in the lower part of the matrix in the next iteration.
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
def find_Kth_smallest(matrix, k):
  n = len(matrix)
  start, end = matrix[0][0], matrix[n - 1][n - 1]
  while start < end:
    mid = start + (end - start) / 2
    smaller, larger = (matrix[0][0], matrix[n - 1][n - 1])

    count, smaller, larger = count_less_equal(matrix, mid, smaller, larger)

    if count == k:
      return smaller
    if count < k:
      start = larger  # search higher
    else:
      end = smaller  # search lower

  return start


def count_less_equal(matrix, mid, smaller, larger):
  count, n = 0, len(matrix)
  row, col = n - 1, 0
  while row >= 0 and col < n:
    if matrix[row][col] > mid:
      # as matrix[row][col] is bigger than the mid, let's keep track of the
      # smallest number greater than the mid
      larger = min(larger, matrix[row][col])
      row -= 1
    else:
      # as matrix[row][col] is less than or equal to the mid, let's keep track of the
      # biggest number less than or equal to the mid
      smaller = max(smaller, matrix[row][col])
      count += row + 1
      col += 1

  return count, smaller, larger

34. Find First and Last Position of Element in Sorted Array

Leetcode: https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

Note:
Binary search should start with 0 and len(nums), not len(nums) - 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def searchRange(self, nums: List[int], target: int) -> List[int]:
    def bs(target): # Where can I insert first target to keep nums sorted
        lo, hi = 0, len(nums)
        while lo < hi:
            mid = math.floor((hi + lo)/2)
            if nums[mid] >= target:
                hi = mid
            else:
                lo = mid + 1
        return lo
    lo = bs(target)
    if target not in nums[lo:lo + 1]:
        return [-1, -1]
    hi = bs(target + 1)  # Where can I insert first target + 1 to keep nums sorted
    return [lo, hi - 1]

33. Search in Rotated Sorted Array

Leetcode: https://leetcode.com/problems/search-in-rotated-sorted-array/

[Solution]

  1. Formula: If a sorted array is shifted, if you take the middle, always one side will be sorted. Take the recursion according to that rule.
  2. 分情况讨论
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def search(self, nums: List[int], target: int) -> int:
    l, r = 0, len(nums) - 1
    while l <= r:
        mid = (l + r) // 2
        if target == nums[mid]:
            return mid
        
        if nums[l] <= nums[mid]:
            # left side acsending
            # search within left side
            if target < nums[mid] and target >= nums[l]:
                r = mid - 1
            else:
                l = mid + 1
        else:
            # nums[0] > nums[mid] since instinct
            # right side acsending
            if target > nums[mid] and target <= nums[r]:
                l = mid + 1
            else:
                r = mid - 1
    return -1

Peak Problem

162. Find Peak Element

Leetcode: https://leetcode.com/problems/find-peak-element/

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

852. Peak Index in a Mountain Array

Leetcode: https://leetcode.com/problems/peak-index-in-a-mountain-array/

Same as above

1
2
3
4
5
6
7
8
9
10
11
12
13
def peakIndexInMountainArray(self, A):
    """
    :type A: List[int]
    :rtype: int
    """
    lo, hi = 0, len(A) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if A[mid] < A[mid + 1]:
            lo = mid + 1
        else:
            hi = mid
    return lo

153. Find Minimum in Rotated Sorted Array

Leetcode: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/

Same as above

1
2
3
4
5
6
7
8
9
def findMin(self, nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < nums[-1]:
            hi = mid
        else:
            lo = mid + 1
    return nums[lo]

410. Split Array Largest Sum

Leetcode: https://leetcode.com/problems/split-array-largest-sum/

Note:

  • The answer has to be between the range [max(nums), sum(nums) + 1).
  • 最少需要多少组k, 使得maximum sum不超过mid
  • Go find k

Narrow down scope problem

81. Search in Rotated Sorted Array II

Leetcode: https://leetcode.com/problems/search-in-rotated-sorted-array-ii/

Note:
The key is to narrow down the searching 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
def search(self, nums, target):
    if not nums:
        return False
    # search for the pivot
    l, r = 0, len(nums) - 1
    while l <= r:
        mid = (l + r) // 2
        if nums[mid] == target:
            return True
        while l < mid and nums[l] == nums[mid]:
            l += 1 # not sure this
        if nums[l] <= nums[mid]:
            # first half is acsending
            if nums[l] <= target < nums[mid]:
                # target in the first half
                r = mid - 1
            else:
                l = mid + 1
        else:
            # second half is acsending
            if nums[mid] < target <= nums[r]:
                l = mid + 1
            else:
                r = mid - 1
    return False

875. Koko Eating Bananas

Leetcode: https://leetcode.com/problems/koko-eating-bananas/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def minEatingSpeed(self, piles: List[int], h: int) -> int:
    # max of k: max(piles)
    # min of k: 1
    # hours = piles[i] // k, if piles[i] % k > 0: hours += 1
    # binary search
    # if sum(hours) > h: k++; elif sum(hours) < h: k--
    def getHour(bite):
        res = 0
        for pile in piles:
            hour = pile // bite
            if pile % bite > 0:
                hour += 1
            res += hour
        return res
    l, r = 1, max(piles)
    while l < r:
        mid = (l + r) // 2
        if getHour(mid) > h:
            # increase bite size
            l = mid + 1
        else:
            r = mid
    return l