23. Binary Search

Table of Contents

A. Introduction

B. LeeCode Problems

704. Binary Search

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

Example:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Code


class Solution:
    def search(self, nums: List[int], target: int) -> int:
        """
         0, 1, 2, 3, 4, 5
        -1, 0, 3, 5, 9, 12
            lr
        0+5//2 = 2
        0+1//2 = 0

        """

        if not nums:
            return -1

        l,r = 0, len(nums)-1

        while l <= r:

            mid = (l + r)//2

            if nums[mid] == target:
                return mid

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

            else:
                r = mid - 1

        return -1

74. Search a 2D Matrix

Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:

Integers in each row are sorted from left to right
The first integer of each row is greater than the last integer of the previous row

Example:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Code

Key Ideas

The matrix can be treated as a sorted array
Perform binary search on the rows to find the row where the target can be found
- If the target is greater than the last element of the row, then the target can be found in the next row
- If the target is less than the first element of the row, then the target can be found in the previous row
Implement 1D binary search on the row to find the target


class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:

        t,b = 0, len(matrix)-1

        while t <= b :

            row = (t+b)//2

            if matrix[row][-1] < target:
                t = row + 1
            elif matrix[row][0] > target:
                b = row - 1
            else:
                break

        if t > b:
            return False

        # binary search on the row
        l,r = 0, len(matrix[0])-1

        while l <= r:

            mid = (l+r)//2

            if matrix[row][mid] == target:
                return True
            elif matrix[row][mid] < target:
                l = mid + 1
            else:
                r = mid -1

        return False

875. Koko Eating Bananas

Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours.

Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.

Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.

Return the minimum integer k such that she can eat all the bananas within h hours.

Example:

Input: piles = [3,6,7,11], h = 8
Output: 4

Key Ideas

The k can be found iteratively using binary search
- Search for a k that satisfies the condition that the number of hours required to eat all the bananas is less than or equal to h
@BaseCase The maximum value of k is the maximum value of the piles

Code


import math

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:

        maxPiles = max(piles)
        l,r = 1, maxPiles
        res = maxPiles

        while l <= r:

            hrs = 0
            k = (l+r)//2
            for pile in piles:
                hrs += math.ceil(pile/k)

            if hrs <= h:
                res = min(res, k)
                r = k-1
            else:
                l = k+1

        return res

4. Median of Two Sorted Arrays

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).

Example:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Key Ideas

@KeyAlgorithm Binary Search on the smaller array to find the partition point
- Move the partition point based on the following condition $$B_{min}\le A_{max} \ \text{and} \ B_{max} \ge A_{min}$$
  - If the above condition is satisfied, then the array is partitioned right
    - Even, median = $(max(A_{min}, B_{min})+min(A_{max}, B_{max}))/2$
    - Odd, median = $min(A_{max}, B_{max})$
  - If $B_{min}$ is greater than $A_{max}$, then l is moved to mid+1
  - If $B_{max}$ is less than $A_{min}$, then r is moved to mid-1

Code


class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:

        if len(nums1) > len(nums2):
            nums2, nums1 = nums1, nums2

        m,n = len(nums1), len(nums2)
        total_len = m+n
        half = total_len//2

        l,r = 0, m-1

        while True:

            a_mid = (l+r)//2
            Amin = nums1[a_mid] if a_mid >= 0 else float("-inf")
            Amax = nums1[a_mid+1] if a_mid+1 < m else float("inf")

            b_mid = half-a_mid-2 # both a_mid and half needs to be zero indexed
            Bmin = nums2[b_mid] if b_mid >= 0 else float("-inf")
            Bmax = nums2[b_mid+1] if b_mid+1 < n else float("inf")

            if Bmin <= Amax and Bmax >= Amin:

                if total_len % 2 == 0:
                    return (max(Amin, Bmin)+min(Amax, Bmax))/2

                return min(Amax, Bmax)

            elif Bmin > Amax:
                l = a_mid + 1
            else:
                r = a_mid - 1