Searching — Linear Search, Binary Search & Search Space Elimination

Module 4 — Searching: Linear Search, Binary Search & Boundary Analysis Structured as Topic → Plain-English Explanation → Real Code → Visual Diagram → Complexity → Common Pitfalls.

1. Linear Search vs Binary Search Mechanics

• Linear Search: Examines every element from index 0 to $n-1$. It requires zero preconditions — works on any array, linked list, or unsorted sequence. In the worst case, it takes $O(n)$ comparisons.
• Binary Search: Operates exclusively on monotonically sorted or partitioned search spaces. By comparing the middle element $mid$ with the target, it instantly eliminates 50% of the entire remaining candidate space. In the worst case, it runs in strictly logarithmic $O(log_2 n)$ time.

// Binary Search with overflow-safe midpoint calculation
int binarySearch(const vector<int>& arr, int target) {
    int lo = 0, hi = arr.size() - 1;
    while (lo <= hi) {
        // Safe against integer overflow (lo + hi can exceed INT_MAX)
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

2. Lower Bound vs Upper Bound Mechanics

In interviews, you frequently need to find the boundaries of duplicate values:

• Lower Bound: The first index $i$ such that $arr[i] ge target$.
• Upper Bound: The first index $i$ such that $arr[i] > target$.
• Count of occurrences: $ ext{upper_bound} - ext{lower_bound}$.

// Lower Bound implementation
int lowerBound(const vector<int>& arr, int target) {
    int lo = 0, hi = arr.size();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] >= target) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

3. Searching in a Rotated Sorted Array

Even when an array is rotated (e.g., [4, 5, 6, 7, 0, 1, 2]), at least one half (left or right) is always normally sorted!

1. Calculate mid.
2. Check if left half (arr[lo] <= arr[mid]) is sorted:
   • If target lies between arr[lo] and arr[mid], narrow search to left half (hi = mid - 1).
   • Otherwise, search right half (lo = mid + 1).
3. Otherwise, right half must be sorted:
   • If target lies between arr[mid] and arr[hi], narrow search to right half (lo = mid + 1).
   • Otherwise, search left half (hi = mid - 1).

Time Complexity remains strictly $O(log n)$.