Searching Algorithms

📖 Introduction

Searching is about finding information efficiently. The first time I reduced a search from O(n) to O(log n), I watched a query that took seconds drop to milliseconds. That experience taught me that choosing the right search strategy can make or break an application's performance.

Binary search in particular is deceptively simple but incredibly powerful. Once you understand that it's not just about "finding an element in a sorted array" but about "searching over any monotonic space," entire categories of problems become solvable.

---

🔍 Linear Search

The simplest approach—check each element sequentially.

def linear_search(arr: list, target) -> int:
    """
    Search for target in unsorted array.
    Time: O(n)
    Space: O(1)
    """
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1


# When to use linear search:
# - Unsorted data
# - Small datasets
# - Single search (not worth sorting first)
# - Linked lists (no random access)

---

⚡ Binary Search

Repeatedly divide search space in half. Requires sorted data.

Basic Binary Search

def binary_search(arr: list[int], target: int) -> int:
    """
    Find target in sorted array.
    Time: O(log n)
    Space: O(1)
    Returns: index if found, -1 otherwise
    """
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = left + (right - left) // 2  # Avoid overflow
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1


# Recursive version
def binary_search_recursive(arr: list[int], target: int, left: int = 0, right: int = None) -> int:
    if right is None:
        right = len(arr) - 1
    
    if left > right:
        return -1
    
    mid = left + (right - left) // 2
    
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)

Python's bisect Module

import bisect

arr = [1, 3, 4, 4, 6, 8]

# bisect_left: leftmost position where target can be inserted
bisect.bisect_left(arr, 4)   # 2 (insert before existing 4s)

# bisect_right: rightmost position where target can be inserted
bisect.bisect_right(arr, 4)  # 4 (insert after existing 4s)

# insort: insert and maintain sorted order
bisect.insort_left(arr, 5)   # arr = [1, 3, 4, 4, 5, 6, 8]


# Finding exact matches
def index_of(arr, target):
    i = bisect.bisect_left(arr, target)
    if i != len(arr) and arr[i] == target:
        return i
    return -1

---

🎯 Binary Search Variations

Find First Occurrence

def find_first(arr: list[int], target: int) -> int:
    """
    Find leftmost/first occurrence of target.
    """
    left, right = 0, len(arr) - 1
    result = -1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if arr[mid] == target:
            result = mid
            right = mid - 1  # Continue searching left
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return result

Find Last Occurrence

def find_last(arr: list[int], target: int) -> int:
    """
    Find rightmost/last occurrence of target.
    """
    left, right = 0, len(arr) - 1
    result = -1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if arr[mid] == target:
            result = mid
            left = mid + 1  # Continue searching right
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return result

Search Range

def search_range(nums: list[int], target: int) -> list[int]:
    """
    Find starting and ending position of target.
    """
    def find_bound(is_left: bool) -> int:
        left, right = 0, len(nums) - 1
        bound = -1
        
        while left <= right:
            mid = left + (right - left) // 2
            
            if nums[mid] == target:
                bound = mid
                if is_left:
                    right = mid - 1
                else:
                    left = mid + 1
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        
        return bound
    
    return [find_bound(True), find_bound(False)]


print(search_range([5, 7, 7, 8, 8, 10], 8))  # [3, 4]

Lower and Upper Bound

def lower_bound(arr: list[int], target: int) -> int:
    """
    Find first position where arr[i] >= target.
    Same as bisect_left.
    """
    left, right = 0, len(arr)
    
    while left < right:
        mid = left + (right - left) // 2
        
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    
    return left


def upper_bound(arr: list[int], target: int) -> int:
    """
    Find first position where arr[i] > target.
    Same as bisect_right.
    """
    left, right = 0, len(arr)
    
    while left < right:
        mid = left + (right - left) // 2
        
        if arr[mid] <= target:
            left = mid + 1
        else:
            right = mid
    
    return left


# Usage
arr = [1, 2, 4, 4, 4, 6, 8]
print(lower_bound(arr, 4))  # 2 (first 4)
print(upper_bound(arr, 4))  # 5 (after last 4)
print(upper_bound(arr, 4) - lower_bound(arr, 4))  # 3 (count of 4s)

---

🔄 Search in Rotated Arrays

Search in Rotated Sorted Array

def search_rotated(nums: list[int], target: int) -> int:
    """
    Search in rotated sorted array (no duplicates).
    [4,5,6,7,0,1,2] is [0,1,2,4,5,6,7] rotated.
    Time: O(log n)
    """
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if nums[mid] == target:
            return mid
        
        # Left half is sorted
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        # Right half is sorted
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    
    return -1


print(search_rotated([4, 5, 6, 7, 0, 1, 2], 0))  # 4

Find Minimum in Rotated Array

def find_min(nums: list[int]) -> int:
    """
    Find minimum in rotated sorted array (no duplicates).
    Time: O(log n)
    """
    left, right = 0, len(nums) - 1
    
    while left < right:
        mid = left + (right - left) // 2
        
        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid
    
    return nums[left]


print(find_min([4, 5, 6, 7, 0, 1, 2]))  # 0


# With duplicates - O(log n) average, O(n) worst
def find_min_duplicates(nums: list[int]) -> int:
    left, right = 0, len(nums) - 1
    
    while left < right:
        mid = left + (right - left) // 2
        
        if nums[mid] > nums[right]:
            left = mid + 1
        elif nums[mid] < nums[right]:
            right = mid
        else:
            right -= 1  # Can't determine, reduce
    
    return nums[left]

---

📊 Search Space Problems

The key insight: binary search works on any monotonic function.

Square Root

def my_sqrt(x: int) -> int:
    """
    Compute floor of square root.
    Search space: [0, x]
    Condition: find largest n where n*n <= x
    """
    if x < 2:
        return x
    
    left, right = 1, x // 2
    
    while left <= right:
        mid = left + (right - left) // 2
        square = mid * mid
        
        if square == x:
            return mid
        elif square < x:
            left = mid + 1
        else:
            right = mid - 1
    
    return right  # Floor of sqrt


# For precise sqrt
def sqrt_precise(x: float, epsilon: float = 1e-10) -> float:
    if x < 0:
        raise ValueError("Cannot compute sqrt of negative")
    if x < 2:
        return x
    
    left, right = 0, x
    
    while right - left > epsilon:
        mid = (left + right) / 2
        if mid * mid < x:
            left = mid
        else:
            right = mid
    
    return (left + right) / 2

Find Peak Element

def find_peak_element(nums: list[int]) -> int:
    """
    Find any peak element (greater than neighbors).
    nums[-1] = nums[n] = -∞
    Time: O(log n)
    """
    left, right = 0, len(nums) - 1
    
    while left < right:
        mid = left + (right - left) // 2
        
        if nums[mid] > nums[mid + 1]:
            right = mid
        else:
            left = mid + 1
    
    return left


print(find_peak_element([1, 2, 3, 1]))  # 2 (index of 3)

Search 2D Matrix

def search_matrix(matrix: list[list[int]], target: int) -> bool:
    """
    Search in row-wise and column-wise sorted matrix.
    Each row's first element > previous row's last element.
    Time: O(log(m*n))
    """
    if not matrix or not matrix[0]:
        return False
    
    rows, cols = len(matrix), len(matrix[0])
    left, right = 0, rows * cols - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        row, col = divmod(mid, cols)
        val = matrix[row][col]
        
        if val == target:
            return True
        elif val < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return False


# For matrix where each row and col is sorted (but not globally)
def search_matrix_ii(matrix: list[list[int]], target: int) -> bool:
    """
    Start from top-right corner.
    Time: O(m + n)
    """
    if not matrix or not matrix[0]:
        return False
    
    row, col = 0, len(matrix[0]) - 1
    
    while row < len(matrix) and col >= 0:
        if matrix[row][col] == target:
            return True
        elif matrix[row][col] > target:
            col -= 1
        else:
            row += 1
    
    return False

Capacity to Ship Packages

def ship_within_days(weights: list[int], days: int) -> int:
    """
    Find minimum ship capacity to ship all packages in 'days' days.
    Binary search on answer.
    """
    def can_ship(capacity: int) -> bool:
        day_count = 1
        current_weight = 0
        
        for w in weights:
            if current_weight + w > capacity:
                day_count += 1
                current_weight = w
            else:
                current_weight += w
        
        return day_count <= days
    
    # Search space: [max_weight, sum_weights]
    left = max(weights)
    right = sum(weights)
    
    while left < right:
        mid = left + (right - left) // 2
        
        if can_ship(mid):
            right = mid
        else:
            left = mid + 1
    
    return left


print(ship_within_days([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5))  # 15

Koko Eating Bananas

def min_eating_speed(piles: list[int], h: int) -> int:
    """
    Find minimum speed k to eat all bananas in h hours.
    Each pile takes ceil(pile/k) hours.
    """
    import math
    
    def can_finish(k: int) -> bool:
        hours = sum(math.ceil(pile / k) for pile in piles)
        return hours <= h
    
    left, right = 1, max(piles)
    
    while left < right:
        mid = left + (right - left) // 2
        
        if can_finish(mid):
            right = mid
        else:
            left = mid + 1
    
    return left


print(min_eating_speed([3, 6, 7, 11], 8))  # 4

Split Array Largest Sum

def split_array(nums: list[int], m: int) -> int:
    """
    Split array into m subarrays to minimize largest sum.
    Binary search on the answer.
    """
    def can_split(max_sum: int) -> bool:
        count = 1
        current_sum = 0
        
        for num in nums:
            if current_sum + num > max_sum:
                count += 1
                current_sum = num
            else:
                current_sum += num
        
        return count <= m
    
    left = max(nums)  # Minimum possible answer
    right = sum(nums)  # Maximum possible answer
    
    while left < right:
        mid = left + (right - left) // 2
        
        if can_split(mid):
            right = mid
        else:
            left = mid + 1
    
    return left


print(split_array([7, 2, 5, 10, 8], 2))  # 18 (split as [7,2,5] and [10,8])

---

🔍 Other Search Techniques

Ternary Search

For unimodal functions (single peak/valley).

def ternary_search(f, left: float, right: float, epsilon: float = 1e-9) -> float:
    """
    Find maximum of unimodal function f on [left, right].
    """
    while right - left > epsilon:
        mid1 = left + (right - left) / 3
        mid2 = right - (right - left) / 3
        
        if f(mid1) < f(mid2):
            left = mid1
        else:
            right = mid2
    
    return (left + right) / 2


# Example: find peak of -x^2 + 4x
result = ternary_search(lambda x: -x**2 + 4*x, 0, 5)  # ~2.0

Exponential Search

When array size is unknown or infinite.

def exponential_search(arr: list[int], target: int) -> int:
    """
    Find target in sorted array.
    Good for unbounded arrays or when target is near beginning.
    Time: O(log i) where i is target's index
    """
    if arr[0] == target:
        return 0
    
    # Find range for binary search
    bound = 1
    while bound < len(arr) and arr[bound] <= target:
        bound *= 2
    
    # Binary search in found range
    left = bound // 2
    right = min(bound, len(arr) - 1)
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1

---

📝 Practice Exercises

Exercise 1: First Bad Version

def first_bad_version(n: int) -> int:
    """
    Versions 1 to n, find first bad version.
    is_bad(version) returns True if bad.
    Minimize calls to is_bad.
    """
    pass

Solution

def first_bad_version(n: int) -> int:
    left, right = 1, n
    
    while left < right:
        mid = left + (right - left) // 2
        
        if is_bad(mid):
            right = mid
        else:
            left = mid + 1
    
    return left

Exercise 2: Find Smallest Letter Greater Than Target

def next_greatest_letter(letters: list[str], target: str) -> str:
    """
    Find smallest letter greater than target.
    Letters wrap around (if target >= last, return first).
    
    Example:
    letters = ["c", "f", "j"], target = "a" -> "c"
    letters = ["c", "f", "j"], target = "c" -> "f"
    letters = ["c", "f", "j"], target = "j" -> "c"
    """
    pass

Solution

def next_greatest_letter(letters: list[str], target: str) -> str:
    left, right = 0, len(letters)
    
    while left < right:
        mid = left + (right - left) // 2
        
        if letters[mid] <= target:
            left = mid + 1
        else:
            right = mid
    
    return letters[left % len(letters)]

Exercise 3: Median of Two Sorted Arrays

def find_median_sorted_arrays(nums1: list[int], nums2: list[int]) -> float:
    """
    Find median of two sorted arrays.
    Time: O(log(min(m, n)))
    
    Example:
    nums1 = [1, 3], nums2 = [2] -> 2.0
    nums1 = [1, 2], nums2 = [3, 4] -> 2.5
    """
    pass

Solution

def find_median_sorted_arrays(nums1: list[int], nums2: list[int]) -> float:
    # Ensure nums1 is smaller
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1
    
    m, n = len(nums1), len(nums2)
    left, right = 0, m
    
    while left <= right:
        partition1 = (left + right) // 2
        partition2 = (m + n + 1) // 2 - partition1
        
        max_left1 = float('-inf') if partition1 == 0 else nums1[partition1 - 1]
        min_right1 = float('inf') if partition1 == m else nums1[partition1]
        
        max_left2 = float('-inf') if partition2 == 0 else nums2[partition2 - 1]
        min_right2 = float('inf') if partition2 == n else nums2[partition2]
        
        if max_left1 <= min_right2 and max_left2 <= min_right1:
            if (m + n) % 2 == 0:
                return (max(max_left1, max_left2) + min(min_right1, min_right2)) / 2
            else:
                return max(max_left1, max_left2)
        elif max_left1 > min_right2:
            right = partition1 - 1
        else:
            left = partition1 + 1
    
    return 0.0

---

🔑 Key Takeaways

1. Binary search achieves O(log n) by halving search space

2. Use bisect module for Python's optimized binary search

3. Search on answer when you can verify a candidate solution

4. Rotated arrays require identifying the sorted portion

5. Template matters: left <= right vs left < right

6. Think monotonically: binary search works on any monotonic property

---

🚀 What's Next?

In the next article, we'll explore dynamic programming:

• Identifying DP problems

• Top-down vs bottom-up approaches

• Classic DP patterns

• Space optimization

Next: Article 12 - Dynamic Programming

---

📚 References

• CLRS Chapter 11: Hash Tables (binary search)

• "Elements of Programming Interviews" - Binary Search chapter

• Python bisect module documentation