Binary Search

Binary Search

What is this problem about?

The "Binary Search interview question" is the quintessential algorithm for efficiently finding an element in a sorted array. Instead of checking every element one by one (linear search), Binary Search repeatedly divides the search interval in half. If the target value is less than the value in the middle of the interval, you narrow the interval to the lower half. Otherwise, you narrow it to the upper half.

Why is this asked in interviews?

This is a "must-know" for any software engineer. Companies from Apple to Google ask the "Binary Search coding problem" to verify a candidate's understanding of logarithmic time complexity ($O(\log N)$). It tests your ability to manage pointers, avoid infinite loops, and handle the "midpoint" calculation correctly to prevent integer overflow.

Algorithmic pattern used

This problem is the foundation of the Binary Search pattern.

1. Pointers: Initialize left = 0 and right = n - 1.
2. Loop: While left <= right:
   • Calculate mid = left + (right - left) / 2.
   • If arr[mid] == target, return mid.
   • If arr[mid] < target, move left = mid + 1.
   • If arr[mid] > target, move right = mid - 1.
3. Return: If the loop ends without finding the target, return -1.

Example explanation

Array: [-1, 0, 3, 5, 9, 12], Target: 9

1. left = 0, right = 5. mid = 2 (Value: 3).
2. 3 < 9, so left = 3, right = 5.
3. mid = 4 (Value: 9).
4. 9 == 9. Return index 4.

Common mistakes candidates make

• Integer Overflow: Using (left + right) / 2 instead of left + (right - left) / 2.
• Termination condition: Using left < right instead of left <= right, which can cause the algorithm to miss the target if it’s at the very end of the range.
• Pointer Update: Using left = mid or right = mid instead of mid + 1 or mid - 1, which can lead to infinite loops.

Interview preparation tip

Binary Search isn't just for finding a number. It can be used on any "sorted" or monotonic space, such as finding a square root or the best price in a range. Master the basic "Binary Search" first, then practice its "Search Insert Position" or "Find First and Last" variations.