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!).
Binary Search ONLY works on Sorted Data. If the data is random, you MUST use a Linear Search O(N).
Middle index.target == Middle, return success.target < Middle, ignore the right half.target > Middle, ignore the left half.while (low <= high) {
int mid = low + (high - low) / 2; // Prevents Integer Overflow!
if (array[mid] == target) return mid;
// ... adjust low/high
}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."