Binary Search is an $O(\log n)$ algorithm used to find the position of a target value within a sorted array. It works by repeatedly dividing the search interval in half.

Think of a Dictionary or a Phonebook:

1. You want to find "Zebra".
2. Open the book exactly in the middle.
3. You see "Mountain".
4. "Zebra" must be in the second half. You can throw away the first half!
5. Open the second half in the middle, and repeat.
6. You find it in just a few flips, rather than checking every single page.

---

The Pre-requisite

The array MUST be sorted. If it's not sorted, you must sort it first ($O(n \log n)$) or use Linear Search ($O(n)$).

Complexity Analysis

• Time: $O(\log n)$. With every step, you eliminate half of the remaining elements.
• Space: $O(1)$ for iterative, $O(\log n)$ for recursive due to the call stack.

Handing Overflow

In many languages, (low + high) / 2 can cause integer overflow if both numbers are large. Better way: low + Math.floor((high - low) / 2).

---

javascript Standard
/**
 * Binary Search - O(log n)
 */
function binarySearch(nums, target) {
  let low = 0;
  let high = nums.length - 1;

  while (low <= high) {
    // Calculate middle with overflow protection
    const mid = low + Math.floor((high - low) / 2);

    if (nums[mid] === target) {
      return mid; // Found it!
    } else if (nums[mid] < target) {
      low = mid + 1; // Target is on the right
    } else {
      high = mid - 1; // Target is on the left
    }
  }

  return -1; // Not found
}

// Example
const arr = [1, 3, 5, 7, 9, 11];
console.log(binarySearch(arr, 7)); // Output: 3

---

Variations

• First/Last Occurrence: Find the index of the first time a target appears in a list with duplicates.
• Search in Nearly Sorted Array: Elements are at most $k$ positions away from their sorted index.
• Square Root: Finding $\sqrt{x}$ using binary search on the range $[0, x]$.

Top Tip: "Binary Search on Answer"

This is a high-level interview technique where you don't search for a value in an array, but rather search for the answer itself in a range of possible values (e.g., "What is the minimum speed needed to finish tasks?").