Search Algorithms: A Refresher

Searching is a fundamental operation in computer science, and understanding search algorithms is essential for coding interviews. Whether you're a new engineer brushing up on the basics or an experienced developer looking for a quick refresher, this guide covers the most important search algorithms, their time complexities, and when to use each.

1. Linear Search (Brute-Force Search)

Overview

Linear search is the simplest search algorithm. It sequentially checks each element in an array or list until it finds the target value or reaches the end.

Time Complexity

• Best case: O(1) (if the target is the first element)

• Worst case: O(n) (if the target is at the end or not present)

• Average case: O(n)

Use Cases

✔️ Small datasets

✔️ Unsorted lists or arrays

✔️ When searching for multiple occurrences of a value

Implementation (Python)

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # Return index of the found element
    return -1  # Target not found

# Example
arr = [3, 5, 2, 9, 4]
print(linear_search(arr, 9))  # Output: 3

2. Binary Search (Divide and Conquer)

Overview

Binary search is much faster than linear search but requires the input to be sorted. It repeatedly divides the search space in half until it finds the target.

Time Complexity

• Best case: O(1) (if the middle element is the target)

• Worst case: O(log n)

• Average case: O(log n)

Use Cases

✔️ Large sorted datasets

✔️ Searching in sorted arrays, binary trees, or dictionaries

✔️ Efficient for range queries

Implementation (Iterative Approach)

def binary_search(arr, target):
    left, right = 0, 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  # Target not found

# Example
arr = [1, 3, 5, 7, 9, 11]
print(binary_search(arr, 7))  # Output: 3

Implementation (Recursive Approach)

def binary_search_recursive(arr, target, left, right):
    if left > right:
        return -1  # Base case: target not found
    
    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)

# Example
arr = [1, 3, 5, 7, 9, 11]
print(binary_search_recursive(arr, 5, 0, len(arr) - 1))  # Output: 2

3. Jump Search (Block Search)

Overview

Jump search is an optimization over linear search for sorted arrays. It skips ahead by a fixed block size (√n) and then performs a linear search within the block where the target might exist.

Time Complexity

• Best case: O(1)

• Worst case: O(√n)

• Average case: O(√n)

Use Cases

✔️ Searching in large sorted datasets where binary search is not ideal

✔️ Scenarios where jumping over blocks is faster than comparing every element

Implementation

import math

def jump_search(arr, target):
    n = len(arr)
    step = int(math.sqrt(n))  # Block size
    prev = 0

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

    for i in range(prev, min(step, n)):  # Linear search within the block
        if arr[i] == target:
            return i
    return -1

# Example
arr = [1, 3, 5, 7, 9, 11, 13, 15]
print(jump_search(arr, 7))  # Output: 3

4. Interpolation Search (Improved Binary Search)

Overview

Interpolation search is an improvement over binary search for uniformly distributed sorted data. Instead of jumping to the middle, it estimates the probable position of the target using a formula.

Time Complexity

• Best case: O(1)

• Worst case: O(n) (if distribution is skewed)

• Average case: O(log log n)

Use Cases

✔️ Large datasets with uniformly distributed values

✔️ Efficient for searching in databases and large sorted arrays

Implementation

def interpolation_search(arr, target):
    low, high = 0, len(arr) - 1

    while low <= high and arr[low] <= target <= arr[high]:
        if low == high:
            return low if arr[low] == target else -1

        pos = low + ((target - arr[low]) * (high - low) // (arr[high] - arr[low]))

        if arr[pos] == target:
            return pos
        elif arr[pos] < target:
            low = pos + 1
        else:
            high = pos - 1

    return -1  # Target not found

# Example
arr = [10, 20, 30, 40, 50, 60, 70]
print(interpolation_search(arr, 40))  # Output: 3

5. Exponential Search (For Unbounded or Large Arrays)

Overview

Exponential search is useful when the size of the array is unknown or very large. It works by doubling the search range (exponentially increasing steps) until the target is within range, then performing binary search.

Time Complexity

• Best case: O(1)

• Worst case: O(log n)

• Average case: O(log n)

Use Cases

✔️ Searching in unbounded lists or infinite-sized arrays

✔️ Large sorted datasets where standard binary search isn't feasible

Implementation

def exponential_search(arr, target):
    if arr[0] == target:
        return 0
    
    index = 1
    while index < len(arr) and arr[index] <= target:
        index *= 2

    return binary_search(arr[:min(index, len(arr))], target)

# Example
arr = [1, 2, 4, 8, 16, 32, 64, 128]
print(exponential_search(arr, 16))  # Output: 4

Summary Table

Algorithm	Best Case	Worst Case	Average Case	When to Use?
Linear Search	O(1)	O(n)	O(n)	Unsorted small datasets
Binary Search	O(1)	O(log n)	O(log n)	Sorted arrays/lists
Jump Search	O(1)	O(√n)	O(√n)	Large sorted arrays
Interpolation Search	O(1)	O(n)	O(log log n)	Uniformly distributed sorted data
Exponential Search	O(1)	O(log n)	O(log n)	Large unknown/unbounded datasets

Mastering these search algorithms will help you ace your technical interviews. Happy coding! 🚀