Binary Search & Search Space PruningPhase 1

### What is Binary Search? Binary Search finds a target in a **sorted array** in **$O(\log N)$ time** by halving the search space at each iteration.

The Golden Equation (Integer Overflow Protection): In languages like C++, Java, or Go with fixed 32-bit integers, calculating `mid` as `(low + high) / 2` can cause **arithmetic overflow** if `low + high > 2,147,483,647`. Use the robust formula: $$\text{mid} = \text{low} + \left\lfloor\frac{\text{high} - \text{low}}{2}\right\rfloor$$

Search Logic: 1. If `arr[mid] === target`: Return `mid`. 2. If `arr[mid] < target`: Target lies in right half ➔ `low = mid + 1`. 3. If `arr[mid] > target`: Target lies in left half ➔ `high = mid - 1`.