Mastering Binary Search

Binary Search is the single most important searching algorithm. It reduces the search space by half in every step. It turns an impossible task (searching 1 trillion records) into a trivial one (only 40 comparisons!).

1. The Requirement (Prerequisite)

Binary Search ONLY works on Sorted Data. If the data is random, you MUST use a Linear Search O(N).

2. Implementation Logic

1. Find the Middle index.
2. If target == Middle, return success.
3. If target < Middle, ignore the right half.
4. If target > Middle, ignore the left half.
5. Repeat.

while (low <= high) {
    int mid = low + (high - low) / 2; // Prevents Integer Overflow!
    if (array[mid] == target) return mid;
    // ... adjust low/high
}

4. Interview Mastery

Q: "Why is `mid = (low + high) / 2` considered a bug in professional code?"

Architect Answer: "Because if `low` and `high` are both large (e.g., 1.5 billion), their sum will exceed the capacity of a 32-bit integer (2.1 billion), resulting in an **Integer Overflow** and a negative number. This will cause an `IndexOutOfRangeException`. The professional fix is `low + (high - low) / 2`, which mathematically achieves the same result without ever risking an overflow."