Binary Search

Binary Search

Linear search is cool, but imagine searching through a phone book by checking every single name from the beginning. That's linear search in a phone book. Binary search is like opening the book to the middle and deciding whether to look in the left half or right half based on what you see. Much smarter, right?

Here's the catch - your array MUST be sorted. Binary search doesn't work on random data. It's like that phone book example - it only works because names are in alphabetical order. If your data isn't sorted, you need to sort it first or stick with linear search.

The magic happens because each step eliminates half the remaining elements. Search space goes from n to n/2 to n/4 to... well, you get it. That's why the time complexity is O(log n) - incredibly fast even for millions of elements. Searching through 1 million elements? At most 20 comparisons. Boom.

Iterative vs Recursive

You can implement binary search two ways: iteratively with a loop or recursively by calling the function on a smaller subarray. Both work, both have the same time complexity. The iterative version is slightly more memory efficient since it doesn't add to the call stack. The recursive version is cleaner and easier to understand for some people.

我个人更喜欢 iterative version because it avoids potential stack overflow issues with very large arrays. But honestly, both are fine for most use cases. Pick whichever makes more sense to you.

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

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

const sorted = [1, 3, 5, 7, 9, 11, 13];
console.log(binarySearch(sorted, 7));
console.log(binarySearch(sorted, 6));