Binary Search

Given an array of integers nums sorted in ascending order and an integer target, return the index of target if it exists in nums, otherwise return -1. The algorithm must run in \(O(\log N)\) time.

Keep a search range [left, right] and compare the middle element with target. If they are equal, return the index. If the middle value is smaller than target, the target can only be in the right half (left = mid + 1); otherwise it can only be in the left half (right = mid - 1). Each step halves the range. The loop condition left <= right keeps the range inclusive, so a single remaining element is still checked. Computing mid = left + (right - left) // 2 avoids integer overflow in languages with fixed-size integers.

def search(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1
    

You are given an m x n integer matrix matrix where each row is sorted in non-decreasing order, and the first integer of each row is greater than the last integer of the previous row. Given an integer target, return True if target is in the matrix, or False otherwise, in \(O(\log (M \cdot N))\) time.

Because every row starts after the previous row ends, reading the matrix row by row gives one fully sorted sequence of \(M \cdot N\) values. Run a single binary search over the virtual indices 0 .. m*n - 1 without actually flattening the matrix. A virtual index mid maps to the cell at row mid // n and column mid % n. Doing one binary search to find the row and a second one to find the column has the same \(O(\log M + \log N) = O(\log (M \cdot N))\) cost, but the single search is simpler to write.

def searchMatrix(matrix: list[list[int]], target: int) -> bool:
    m, n = len(matrix), len(matrix[0])
    left, right = 0, m * n - 1
    while left <= right:
        mid = left + (right - left) // 2
        value = matrix[mid // n][mid % n]
        if value == target:
            return True
        elif value < target:
            left = mid + 1
        else:
            right = mid - 1
    return False
    

Given an integer array nums and an integer k, return the k-th largest element in the array. Note that it is the k-th largest element in sorted order, not the k-th distinct element.

Sorting costs \(O(N \log N)\), and a min-heap of size k costs \(O(N \log k)\) with a guaranteed worst case. The fastest approach on average is Quickselect, which uses the partition step of Quicksort but only continues into the one side that contains the answer. The k-th largest element is at index N - k in ascending order. Pick a random pivot (this makes the \(O(N^2)\) worst case extremely unlikely) and partition the current range into three parts: values less than the pivot, equal to the pivot, and greater than the pivot. If the target index falls inside the "equal" part, the pivot is the answer; otherwise repeat on the side that contains the target index. The three-way split keeps the algorithm fast when the array has many duplicates. The work shrinks geometrically on average (\(N + N/2 + N/4 + \dots\)), giving \(O(N)\) expected time.

import random

def findKthLargest(nums: list[int], k: int) -> int:
    target = len(nums) - k  # index of the answer in ascending order
    left, right = 0, len(nums) - 1

    while True:
        pivot = nums[random.randint(left, right)]

        # Three-way partition of nums[left..right]:
        # [left, lt) < pivot, [lt, gt] == pivot, (gt, right] > pivot
        lt, i, gt = left, left, right
        while i <= gt:
            if nums[i] < pivot:
                nums[lt], nums[i] = nums[i], nums[lt]
                lt += 1
                i += 1
            elif nums[i] > pivot:
                nums[i], nums[gt] = nums[gt], nums[i]
                gt -= 1
            else:
                i += 1

        if target < lt:
            right = lt - 1
        elif target > gt:
            left = gt + 1
        else:
            return nums[target]
    

Design a data structure that supports adding integers from a data stream and finding the median of all elements added so far. Implement addNum(num) and findMedian(). The median is the middle value of the sorted list, or the average of the two middle values if the count is even.

Keep the data split into two halves using two heaps: a max-heap small holding the smaller half and a min-heap large holding the larger half. Python only has a min-heap, so the max-heap stores negated values. Maintain two invariants: every value in small is less than or equal to every value in large, and small is either the same size as large or exactly one element bigger. With these, the median is the top of small (odd count) or the average of both tops (even count), available in \(O(1)\).

To add a number, push it into small, then move the largest value of small to large. This guarantees the ordering invariant. If large is now bigger than small, move its smallest value back to small to restore the size invariant. Each insertion uses a constant number of heap operations.

import heapq

class MedianFinder:
    def __init__(self):
        self.small = []  # max-heap (store negatives): smaller half
        self.large = []  # min-heap: larger half

    def addNum(self, num: int) -> None:
        heapq.heappush(self.small, -num)
        # Move the largest of the small half to the large half
        heapq.heappush(self.large, -heapq.heappop(self.small))
        # Keep small the same size as large, or one bigger
        if len(self.large) > len(self.small):
            heapq.heappush(self.small, -heapq.heappop(self.large))

    def findMedian(self) -> float:
        if len(self.small) > len(self.large):
            return -self.small[0]
        return (-self.small[0] + self.large[0]) / 2