Searching Algorithms

Introduction

Searching is one of the most fundamental operations in computing. Whether you're looking up a word in a dictionary, finding a file on your computer, or querying a database, you're performing a search. Understanding different search algorithms and when to use them is essential.

Learning Objectives

By the end of this reading, you will be able to:

• Implement linear and binary search
• Understand when each search method is appropriate
• Apply search algorithms to solve problems
• Analyze search algorithm complexity

1. Linear Search

The simplest search: check each element until you find the target.

Implementation

def linear_search(arr, target):
    """
    Search for target in array.
    Returns index if found, -1 if not found.
    Time: O(n), Space: O(1)
    """
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

With Python's Built-in

# Using index() - raises ValueError if not found
try:
    index = arr.index(target)
except ValueError:
    index = -1

# Using in - just checks existence
if target in arr:
    print("Found!")

Complexity Analysis

• Best case: O(1) - target is first element
• Worst case: O(n) - target is last or not present
• Average case: O(n) - target is in middle on average
• Space: O(1)

When to Use

• Unsorted data
• Small datasets
• One-time searches
• Linked lists (no random access)

2. Binary Search

Efficient search for sorted arrays: repeatedly halve the search space.

Implementation (Iterative)

def binary_search(arr, target):
    """
    Search for target in SORTED array.
    Returns index if found, -1 if not found.
    Time: O(log n), Space: O(1)
    """
    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

Implementation (Recursive)

def binary_search_recursive(arr, target, left=0, right=None):
    """
    Recursive binary search.
    Time: O(log n), Space: O(log n) for call stack
    """
    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)

How It Works

Array: [1, 3, 5, 7, 9, 11, 13, 15]
Target: 9

Step 1: left=0, right=7, mid=3, arr[3]=7 < 9
        Search right half: left=4

Step 2: left=4, right=7, mid=5, arr[5]=11 > 9
        Search left half: right=4

Step 3: left=4, right=4, mid=4, arr[4]=9 = target
        Found at index 4!

Complexity Analysis

• Best case: O(1) - target is middle element
• Worst case: O(log n) - maximum halvings needed
• Average case: O(log n)
• Space: O(1) iterative, O(log n) recursive

Why O(log n)?

Each comparison eliminates half the remaining elements: n → n/2 → n/4 → ... → 1

Number of halvings: log₂(n)

3. Binary Search Variations

Find First Occurrence

def find_first(arr, target):
    """Find leftmost 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  # Keep searching left
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return result

Find Last Occurrence

def find_last(arr, target):
    """Find rightmost 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  # Keep searching right
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return result

Find Insert Position

def find_insert_position(arr, target):
    """
    Find index where target should be inserted to maintain sorted order.
    (Lower bound - first position where arr[i] >= target)
    """
    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

Python's bisect Module

import bisect

arr = [1, 3, 5, 7, 9, 11]

# Find insert position
bisect.bisect_left(arr, 6)   # 3 (first position where val >= 6)
bisect.bisect_right(arr, 7)  # 4 (first position where val > 7)

# Insert while maintaining order
bisect.insort_left(arr, 6)   # arr is now [1, 3, 5, 6, 7, 9, 11]

4. Binary Search on Answer

Use binary search to find the answer to optimization problems.

Example: Square Root

def sqrt_floor(n):
    """Find floor of square root."""
    if n < 2:
        return n

    left, right = 1, n // 2

    while left <= right:
        mid = left + (right - left) // 2
        square = mid * mid

        if square == n:
            return mid
        elif square < n:
            left = mid + 1
        else:
            right = mid - 1

    return right  # Floor of sqrt

Example: Minimum Capacity

def min_capacity(weights, days):
    """
    Find minimum ship capacity to ship all packages in 'days' days.
    Packages must be shipped in order.
    """
    def can_ship(capacity):
        current_load = 0
        days_needed = 1
        for weight in weights:
            if current_load + weight > capacity:
                days_needed += 1
                current_load = weight
            else:
                current_load += weight
        return days_needed <= days

    left = max(weights)  # At least fit largest package
    right = sum(weights)  # Ship everything in one day

    while left < right:
        mid = left + (right - left) // 2
        if can_ship(mid):
            right = mid
        else:
            left = mid + 1

    return left

5. Search in Special Arrays

Rotated Sorted Array

def search_rotated(arr, target):
    """
    Search in array that was sorted then rotated.
    [4, 5, 6, 7, 0, 1, 2] - rotated at pivot
    """
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = left + (right - left) // 2

        if arr[mid] == target:
            return mid

        # Determine which half is sorted
        if arr[left] <= arr[mid]:  # Left half sorted
            if arr[left] <= target < arr[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:  # Right half sorted
            if arr[mid] < target <= arr[right]:
                left = mid + 1
            else:
                right = mid - 1

    return -1

Find Peak Element

def find_peak(arr):
    """Find any peak element (greater than neighbors)."""
    left, right = 0, len(arr) - 1

    while left < right:
        mid = left + (right - left) // 2

        if arr[mid] < arr[mid + 1]:
            left = mid + 1  # Peak is to the right
        else:
            right = mid  # Peak is at mid or left

    return left

Search in 2D Matrix

def search_matrix(matrix, target):
    """
    Search in row-wise and column-wise sorted matrix.
    Start from top-right corner.
    """
    if not matrix:
        return False

    rows, cols = len(matrix), len(matrix[0])
    row, col = 0, cols - 1

    while row < rows and col >= 0:
        if matrix[row][col] == target:
            return True
        elif matrix[row][col] > target:
            col -= 1
        else:
            row += 1

    return False

6. Ternary Search

For unimodal functions (one peak/valley), finds the extremum.

def ternary_search_max(f, left, right, epsilon=1e-9):
    """Find x that maximizes f(x) for unimodal function."""
    while right - left > epsilon:
        m1 = left + (right - left) / 3
        m2 = right - (right - left) / 3

        if f(m1) < f(m2):
            left = m1
        else:
            right = m2

    return (left + right) / 2

7. Jump Search

For sorted arrays - jump ahead by √n, then linear search.

import math

def jump_search(arr, target):
    """
    Time: O(√n), Space: O(1)
    Good when binary search's random access is costly.
    """
    n = len(arr)
    step = int(math.sqrt(n))

    prev = 0
    while arr[min(step, n) - 1] < target:
        prev = step
        step += int(math.sqrt(n))
        if prev >= n:
            return -1

    # Linear search in block
    while arr[prev] < target:
        prev += 1
        if prev == min(step, n):
            return -1

    if arr[prev] == target:
        return prev

    return -1

8. Exponential Search

Find range, then binary search. Good for unbounded arrays.

def exponential_search(arr, target):
    """
    Time: O(log n), works well when target is near beginning.
    """
    if arr[0] == target:
        return 0

    n = len(arr)
    bound = 1

    # Find range for binary search
    while bound < n and arr[bound] < target:
        bound *= 2

    # Binary search in found range
    left = bound // 2
    right = min(bound, n - 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

9. Search Algorithm Comparison

*Average case for uniformly distributed data

10. Common Patterns

Binary Search Template

def binary_search_template(arr, target):
    left, right = 0, len(arr)  # or len(arr) - 1

    while left < right:  # or left <= right
        mid = left + (right - left) // 2

        if condition(mid):
            right = mid  # or right = mid - 1
        else:
            left = mid + 1

    return left  # or check if arr[left] == target

Finding Boundary

def find_boundary(arr):
    """Find first True in [False, False, ..., True, True, ...]"""
    left, right = 0, len(arr) - 1

    while left < right:
        mid = left + (right - left) // 2
        if arr[mid]:
            right = mid
        else:
            left = mid + 1

    return left if arr[left] else -1

Exercises

Basic

1. Implement linear search that returns all indices where target appears.

2. Use binary search to find how many times a sorted array has been rotated.

3. Find the first and last position of a target in a sorted array with duplicates.

Intermediate

4. Find the smallest element in a rotated sorted array.

5. Given a sorted array, find a pair with sum equal to target (O(n) time).

6. Implement binary search for a function that returns True/False (find first True).

Advanced

7. Find the median of two sorted arrays in O(log(min(m,n))) time.

8. Search in an array where differences between adjacent elements is at most 1 (step array).

9. Given a function f(x) that increases then decreases, find the maximum value.

Summary

• Linear search: O(n), works on any data
• Binary search: O(log n), requires sorted data
• Binary search variations: find first/last, insert position
• Binary search on answer: solve optimization problems
• Choose based on: data organization, search frequency, data size
• Always verify: array is sorted before binary search!

Next Reading

Sorting Algorithms →