11. Searching Algorithms

Overview of Searching Algorithms

Searching is the process of locating a particular element (the key) within a collection of data. The efficiency of a search depends on the structure of the data and the algorithm employed. This chapter covers the most common searching techniques taught in a Data Structures and Algorithms course, ranging from the simplest linear scan to more sophisticated divide‑and‑conquer methods such as binary, ternary, and their variations.

1. Linear Search

Linear search, also known as sequential search, examines each element of the array in order until the key is found or the end of the array is reached.

Pseudocode

for i = 0 to n‑1:
    if A[i] == key:
        return i
return -1

Complexity Analysis

• Time: Worst‑case O(n) (key not present or at last index); best‑case O(1) when the key is at index 0.
• Space: O(1) auxiliary space.

Example

Searching for 7 in the array [4, 2, 7, 9]:

1. Compare A[0] = 4 → not equal.
2. Compare A[1] = 2 → not equal.
3. Compare A[2] = 7 → match found; return index 2.

When to Use

Linear search is appropriate for small datasets, unsorted data, or when the cost of sorting outweighs the search benefit.

2. Binary Search

Binary search improves upon linear search by requiring the array to be sorted. It repeatedly halves the search interval, achieving logarithmic time.

Pseudocode (Iterative)

low = 0; high = n‑1
while low ≤ high:
    mid = (low + high) // 2
    if A[mid] == key:
        return mid
    elif A[mid] < key:
        low = mid + 1
    else:
        high = mid - 1
return -1

Complexity Analysis

• Time: O(log n) in worst case; best case O(1) when the middle element equals the key.
• Space: O(1) for the iterative version; recursive version uses O(log n) stack space.

Step‑by‑Step Example

Search for 15 in the sorted array [1,3,5,7,9,11,13,15,17] (indices 0‑8):

1. Initial: low=0, high=8 → mid=4 (value 9). Since 9 < 15, set low=5.
2. Now low=5, high=8 → mid=6 (value 13). 13 < 15 → low=7.
3. Now low=7, high=8 → mid=7 (value 15). Match found; return index 7.

Variations of Binary Search

Binary search can be adapted to solve several related problems without changing its asymptotic complexity.

Lower Bound (first element ≥ key)

Returns the smallest index of first element not less than key; if all < key returns n. Useful for inserting while maintaining order.

Upper Bound (first element > key)

index of first element greater than key.

Count of occurrences = upper_bound – lower_bound.

Example

Array [2,4,4,4,7,9], key=4:

• Lower bound → index 1 (first 4).
• Upper bound → index 4 (first element >4, which is 7).
• Count = 4 – 1 = 3 occurrences.

Search in Rotated Sorted Array

Determine which half is properly sorted, then decide side. Still O(log n).

Pseudocode (Conceptual)

while low ≤ high:
    mid = (low + high) // 2
    if A[mid] == key: return mid
    // left half sorted?
    if A[low] ≤ A[mid]:
        if A[low] ≤ key < A[mid]:
            high = mid - 1
        else:
            low = mid + 1
    else: // right half sorted
        if A[mid] < key ≤ A[high]:
            low = mid + 1
        else:
            high = mid - 1
return -1

Nearest Smaller / Greater Element

Modify condition to track candidate while discarding half.

3. Ternary Search

Applicable to unimodal functions (increase then decrease) on a discrete domain. Divides range into three parts using mid1 = l + (r‑l)/3, mid2 = r – (r‑l)/3. Compare f(mid1) and f(mid2); discard left or right third accordingly.

Pseudocode

while r‑l > 2:
    m1 = l + (r‑l)//3
    m2 = r - (r‑l)//3
    if f(m1) < f(m2): l = m1+1
    else: r = m2-1
check remaining few points linearly.

Complexity Analysis

• Time: O(log₃ n) ≈ O(log n).
• Space: O(1) iterative; O(log n) recursive due to stack.

Example: find maximum of f(x) = -(x‑5)² + 20 on integers 0..10.

Iterations converge to x=5.

4. Practical Applications

• Database indexing (B‑tree, hash) uses binary search within leaf pages.
• Autocomplete: binary search on sorted dictionary to find prefix range.
• Version control: binary search to locate first bad commit (git bisect).
• Numerical methods: solving equations via binary search on answer (e.g., square root).
• Competitive programming: searching for threshold in monotonic predicate.

5. Summary Table

6. Key Takeaways

1. Match algorithm to data structure: linear for unsorted/small, binary for sorted, ternary for unimodal.
2. Binary search’s adaptations (lower/upper bound, rotated arrays, nearest neighbor) retain O(log n) complexity.
3. Correctly identifying monotonicity or unimodality is essential for binary/ternary search.
4. Real‑world systems (databases, autocomplete, version control) rely on these search primitives for efficiency.

“Searching is not just about finding an element; it’s about eliminating half of the possibilities with each comparison.” – Adapted from classic DSA literature.