🔍 Searching — Complete Guide

Index: Searching Index | Parent: Array Index

The Two Core Searches

Type	Array Type	Time	Use When
Linear Search	Any	O(n)	Unsorted, small, unknown structure
Binary Search	Sorted only	O(log n)	Sorted array, fast lookup needed

Linear Search

Concept: Check every element one by one from left to right.

function linearSearch(array $arr, mixed $target): int {
    foreach ($arr as $index => $value) {
        if ($value === $target) return $index;
    }
    return -1; // not found
}

echo linearSearch([5, 3, 8, 1, 9], 8); // 2
echo linearSearch([5, 3, 8, 1, 9], 7); // -1

function linearSearch(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) return i;
    }
    return -1;
}

Time: O(n) | Space: O(1)

Binary Search — The Most Important Search

RULE: Array MUST be sorted. Always.

Concept: Cut search space in half each time.

Look at middle element
If target == mid → found
If target < mid → search LEFT half
If target > mid → search RIGHT half

Search 7 in [1, 3, 5, 7, 9, 11, 13]
              L        M           R
              mid = arr[3] = 7 ✅ Found!

Search 5 in [1, 3, 5, 7, 9, 11, 13]
              L        M           R
              mid = 7, target 5 < 7 → go LEFT
              L   M   R
              mid = 3, target 5 > 3 → go RIGHT
                  L=M=R
                  mid = 5 ✅ Found!

Iterative Binary Search (Preferred)

function binarySearch(array $arr, int $target): int {
    $left  = 0;
    $right = count($arr) - 1;

    while ($left <= $right) {
        $mid = $left + intdiv($right - $left, 2); // avoid overflow

        if ($arr[$mid] === $target) return $mid;
        if ($arr[$mid] < $target)   $left = $mid + 1;
        else                         $right = $mid - 1;
    }

    return -1; // not found
}

function binarySearch(arr, target) {
    let left = 0, right = arr.length - 1;
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        if (arr[mid] === target) return mid;
        if (arr[mid] < target)   left  = mid + 1;
        else                      right = mid - 1;
    }
    return -1;
}

Recursive Binary Search

function binarySearchRecursive(array $arr, int $target, int $left, int $right): int {
    if ($left > $right) return -1;

    $mid = $left + intdiv($right - $left, 2);

    if ($arr[$mid] === $target) return $mid;
    if ($arr[$mid] < $target)   return binarySearchRecursive($arr, $target, $mid + 1, $right);
    return binarySearchRecursive($arr, $target, $left, $mid - 1);
}

Time: O(log n) | Space: O(1) iterative, O(log n) recursive

Binary Search Variants (Interview Favorites!)

Variant 1: Find First Occurrence of Target

[1, 2, 2, 2, 3, 4]  target=2
         ^first = index 1

function firstOccurrence(array $arr, int $target): int {
    $left = 0;
    $right = count($arr) - 1;
    $result = -1;

    while ($left <= $right) {
        $mid = $left + intdiv($right - $left, 2);
        if ($arr[$mid] === $target) {
            $result = $mid;     // record but keep searching LEFT
            $right = $mid - 1;
        } elseif ($arr[$mid] < $target) {
            $left = $mid + 1;
        } else {
            $right = $mid - 1;
        }
    }
    return $result;
}

Variant 2: Find Last Occurrence of Target

function lastOccurrence(array $arr, int $target): int {
    $left = 0;
    $right = count($arr) - 1;
    $result = -1;

    while ($left <= $right) {
        $mid = $left + intdiv($right - $left, 2);
        if ($arr[$mid] === $target) {
            $result = $mid;     // record but keep searching RIGHT
            $left = $mid + 1;
        } elseif ($arr[$mid] < $target) {
            $left = $mid + 1;
        } else {
            $right = $mid - 1;
        }
    }
    return $result;
}

Variant 3: Count Occurrences

function countOccurrences(array $arr, int $target): int {
    $first = firstOccurrence($arr, $target);
    if ($first === -1) return 0;
    $last = lastOccurrence($arr, $target);
    return $last - $first + 1;
}

echo countOccurrences([1,2,2,2,3,4], 2); // 3

Variant 4: Find Insert Position (Lower Bound)

Question: Where would target go if inserted to keep sorted order?

function lowerBound(array $arr, int $target): int {
    $left = 0;
    $right = count($arr);

    while ($left < $right) {
        $mid = $left + intdiv($right - $left, 2);
        if ($arr[$mid] < $target) {
            $left = $mid + 1;
        } else {
            $right = $mid;
        }
    }
    return $left; // index of first element >= target
}

echo lowerBound([1,3,5,7,9], 6); // 3 (would insert at index 3)

Variant 5: Search in Rotated Sorted Array `[M][FB]`

Question: [4,5,6,7,0,1,2], find 0 → return index 4.

🧠 How to Approach This

Step 1 — Recognize the pattern:

Binary search on a rotated sorted array. The key property: even after rotation, one half is ALWAYS fully sorted.

Step 2 — Brute force:

Linear scan: O(n). We want O(log n).

Step 3 — Optimal insight:

When you compute mid, either the LEFT half [left..mid] or RIGHT half [mid..right] is guaranteed to be sorted. Determine which is sorted by comparing arr[left] and arr[mid]. Then check if target falls within the sorted half.

Step 4 — Algorithm:

1. Standard binary search setup (L, R, mid)

2. If arr[mid] == target: return mid

3. If arr[left] <= arr[mid]: left half is sorted

- If target in [arr[left], arr[mid]): search left

- Else: search right

4. Else: right half is sorted

- If target in (arr[mid], arr[right]]: search right

- Else: search left

Step 5 — Edge cases:

- Not rotated at all: normal binary search

- Rotated by 1: still works

- Duplicates: harder case, may need linear scan in worst case

function searchRotated(array $arr, int $target): int {
    $left = 0;
    $right = count($arr) - 1;

    while ($left <= $right) {
        $mid = $left + intdiv($right - $left, 2);
        if ($arr[$mid] === $target) return $mid;

        // Left half is sorted
        if ($arr[$left] <= $arr[$mid]) {
            if ($target >= $arr[$left] && $target < $arr[$mid]) {
                $right = $mid - 1; // target in left half
            } else {
                $left = $mid + 1;  // target in right half
            }
        }
        // Right half is sorted
        else {
            if ($target > $arr[$mid] && $target <= $arr[$right]) {
                $left = $mid + 1;  // target in right half
            } else {
                $right = $mid - 1; // target in left half
            }
        }
    }
    return -1;
}

echo searchRotated([4,5,6,7,0,1,2], 0); // 4

Variant 6: Find Peak Element `[M]`

Question: Find any element greater than its neighbors.

🧠 How to Approach This

Step 1 — Key insight:

If arr[mid] > arr[mid+1], the peak is in the left half (or mid itself). Otherwise, peak is in the right half. This guarantees the binary search converges to a peak.

Step 2 — Why this works:

The problem guarantees arr[-1] = arr[n] = -∞. So the array always "rises" to a peak somewhere.

If arr[mid] < arr[mid+1]: arr[mid+1] is higher, and since arr[n]=-∞ at some point we must come back down → there's a peak in [mid+1, right].

Step 3 — Algorithm:

1. L=0, R=n-1

2. While L < R: mid = (L+R)/2

3. If arr[mid] > arr[mid+1]: R = mid (peak in left including mid)

4. Else: L = mid+1 (peak in right half)

5. Return L (convergence point is a peak)

function findPeak(array $arr): int { $left = 0; $right = count($arr) - 1;

while ($left < $right) { $mid = $left + intdiv($right - $left, 2); if ($arr[$mid] > $arr[$mid + 1]) { $right = $mid; // peak is in left half (including mid) } else { $left = $mid + 1; // peak is in right half } } return $left; // index of peak }

echo findPeak([1,2,3,1]); // 2 (value 3) echo findPeak([1,2,1,3,5,6,4]); // 5 (value 6)


### Variant 7: Find Minimum in Rotated Sorted Array

function findMin(array $arr): int { $left = 0; $right = count($arr) - 1;

while ($left < $right) { $mid = $left + intdiv($right - $left, 2);

if ($arr[$mid] > $arr[$right]) { $left = $mid + 1; // min is in right half } else { $right = $mid; // min is in left half (including mid) } } return $arr[$left]; }

echo findMin([4,5,6,7,0,1,2]); // 0


---

## Binary Search on Answer (Advanced Pattern)

**Concept:** When finding an optimal VALUE (not index), binary search on the answer space.

**Template:**

// "Find minimum X such that condition(X) is true" function binarySearchOnAnswer(array $arr): int { $left = minPossibleAnswer; $right = maxPossibleAnswer;

while ($left < $right) { $mid = $left + intdiv($right - $left, 2); if (condition($arr, $mid)) { $right = $mid; // try smaller } else { $left = $mid + 1; // too small, try larger } } return $left; }


**Example:** Koko eating bananas — find minimum eating speed.

function minEatingSpeed(array $piles, int $h): int { $left = 1; $right = max($piles);

while ($left < $right) { $mid = $left + intdiv($right - $left, 2);

// Can Koko eat all piles in h hours at speed mid? $hours = array_reduce($piles, fn($carry, $p) => $carry + (int)ceil($p / $mid), 0);

if ($hours <= $h) { $right = $mid; // possible, try slower } else { $left = $mid + 1; // too slow } } return $left; }


---

## Interview Questions — Searching

---

### Q1. Find element in 2D sorted matrix `[M][FB]`

**Question:** Matrix where each row and column is sorted. Find target.

**Way of Thinking:**
> Start from top-right corner. If target < current → go left. If target > current → go down.

function searchMatrix(array $matrix, int $target): bool { if (empty($matrix)) return false;

$row = 0; $col = count($matrix[0]) - 1;

while ($row < count($matrix) && $col >= 0) { if ($matrix[$row][$col] === $target) return true; if ($matrix[$row][$col] > $target) $col--; else $row++; } return false; }

$matrix = [[1,4,7],[2,5,8],[3,6,9]]; var_dump(searchMatrix($matrix, 5)); // true var_dump(searchMatrix($matrix, 10)); // false


**Time:** O(m+n) | **Space:** O(1)

---

### Q2. Binary Search in PHP (Laravel context) `[E][L]`

// Laravel: find item in sorted collection $users = collect(range(1, 1000000))->map(fn($i) => ['id' => $i, 'name' => "User $i"]);

// Bad: O(n) linear search $user = $users->first(fn($u) => $u['id'] === 500000);

// Good: sort by id then binary search // In practice: use DB query with index → O(log n) naturally User::find(500000); // DB uses B-tree index = binary search!

// PHP built-in for sorted arrays: $sorted = [1, 3, 5, 7, 9, 11, 13, 15]; // No built-in binary search — implement manually or use: echo array_search(7, $sorted); // linear, O(n)


---

### Q3. Find Square Root (without sqrt()) `[M]`

**Way of Thinking:**
> Binary search on the answer. Find largest x where x*x <= n.

function mySqrt(int $n): int { if ($n < 2) return $n;

$left = 1; $right = intdiv($n, 2);

while ($left <= $right) { $mid = $left + intdiv($right - $left, 2); $sq = $mid * $mid;

if ($sq === $n) return $mid; elseif ($sq < $n) $left = $mid + 1; else $right = $mid - 1; }

return $right; // floor of sqrt }

echo mySqrt(16); // 4 echo mySqrt(10); // 3 (floor of 3.16...)