Binary Search Fundamentals

1. Introduction

What is Binary Search?

Binary Search is an efficient searching algorithm that operates on sorted collections. It repeatedly halves the size of the search space, checking the middle element and narrowing the target range until the element is found or the range becomes empty.

Why is it Important?

Linear search takes O(N) comparisons. Binary Search takes only O(log N) comparisons. At scale, this difference is staggering:

For N = 1,000,000 (1 million), linear search takes up to 1,000,000 steps. Binary search takes at most 20 steps.

For N = 1,000,000,000 (1 billion), binary search takes at most 30 steps.

Where is it Used?

Git Bisect: Finding the exact commit that introduced a bug via a binary search on the commit history.

Database Lookups: Retrieving records from B-tree indices in logarithmic time.

Compiler Optimizations: Locating symbol table references quickly.

---

2. Mental Model: The Guessing Game

Imagine someone asks you to guess a number between 1 and 100.

If you guess 50, they tell you: "My number is higher."

Instantly, you discard the entire lower half [1..50]. Your new search space is [51..100].

You guess the midpoint of the new range: 75. They tell you: "My number is lower."

You discard the upper half [75..100]. Your new search space is [51..74].

Each guess costs O(1) time, but eliminates 50\% of the possibilities. This geometric decay is the essence of logarithmic time complexity.

---

3. Core Concepts & Implementations

1. Invariant & Termination

In exact-match binary search, we maintain the loop invariant that the target is within the range [lo, hi].

We initialize lo = 0 and hi = n - 1.

The loop condition is while (lo <= hi) because if lo == hi, there is still one element left to check.

When lo > hi, the search space is empty, indicating the target is not present.

2. Avoiding Integer Overflow

A common rookie mistake is calculating mid as int mid = (lo + hi) / 2. If the sum of lo and hi exceeds the maximum integer capacity (2^31 - 1 in Java/C++), it overflows to a negative number, causing index-out-of-bounds errors. Always use the safe formula:

---

4. Visual Trace: Finding Target = 13

Let's search for 13 in the sorted array [2, 5, 8, 12, 13, 17, 20]:

---

5. Real-World Applications

IP Routing Tables: Resolving destination IP prefixes using CIDR mask matching.

Database B-Tree Indexes: B-Trees generalize binary search by splitting search paths into B branches instead of 2, speeding up disk block reads.

---

6. Interview Perspective

How Interviewers Ask This Topic

Interviewers test basic setup invariants:

"Implement binary search without using comparison operators if possible."

"Given a sorted array, write a program to check if an element exists."

Rotate arrays or modify conditions to see if you can adapt the binary search logic.

Common Mistakes

> 2. Infinite Loops: Forgetting to update boundary parameters (lo = mid + 1 or hi = mid - 1) and instead setting lo = mid or hi = mid can lead to infinite loops when lo and hi differ by 1.

---

7. Summary

Requirement: Input must be sorted or monotonic.

Complexity: Time complexity is O(log N); space complexity is O(1).

Overflow Avoidance: Always calculate midpoint as lo + (hi - lo) / 2.

Termination: Use lo <= hi for exact matches, and adjust boundaries excluding mid.

---

8. Quiz

Question 1: What is the maximum number of comparisons needed to search for an element in a sorted array of size 1024?

Answer: 11 comparisons. log_2(1024) = 10. If the target is not found, we perform one final check when the loop condition terminates, making it at most 11 checks.

Question 2: What is the consequence of calculating mid as (lo + hi) / 2 in Java or C++?

Answer: If lo + hi exceeds 2^31 - 1, it overflows to a negative integer. Dividing a negative number by 2 yields a negative index, causing an ArrayIndexOutOfBoundsException.

Question 3: If an array contains duplicates, does the standard exact-match template guarantee finding the first occurrence?

Answer: No. The exact-match template returns the index of any matching element it encounters first, which depends on the position of the elements. To find the first occurrence, a boundary template must be used.

Question 4: What is the recurrence relation for Binary Search?

Answer: T(N) = T(N/2) + O(1). According to Case 2 of the Master Theorem, this evaluates to O(log N).

Question 5: Can you apply binary search on a sorted Singly Linked List?

Answer: You can, but it is highly inefficient. Because linked lists lack random access, finding mid takes O(N) traversal steps. This degrades the overall search time to O(N), defeating the purpose of binary search.