Binary Search

Introduction

Search a sorted array in O(log n) by repeatedly halving the range. Foundation of countless interview problems.

Beginner analogy: think of arrays as a row of numbered lockers — given the locker number you can open it instantly, but adding a new locker in the middle means renumbering every locker after it. Strings are simply arrays of letters arranged in the same way.

In this lesson we will walk through Binary Search step by step, see exactly how the operation works in memory, look at the time and space complexity, study a real-world coding example and finish with senior-level interview questions you will absolutely face at FAANG, Microsoft, Atlassian, Stripe and every modern engineering team.

Understanding the topic

Core concepts to understand:

• 🧠 Clear definition and mental model of binary search.
• 📦 Memory layout and how the CPU accesses elements.
• ⏱ Time and space complexity — best, average, worst.
• 🔧 Step-by-step implementation in clean, readable code.
• 🎯 Common variants and follow-up interview questions.
• 🚧 Pitfalls: off-by-one, integer overflow, mutating during iteration.
• 🏢 Real production scenarios where this technique appears.

Syntax reference

Visual workflow / architecture:

Array  +  Target
      |
      v
   Algorithm
      |
      v
Loop / Recurse
      |
      v
State Update
      |
      v
   Result

Informative example

Implementation in Java, Python, C++ and JavaScript:

Binary search halves the search space each step. We compare the middle element to the target and discard the half that cannot contain it — O(log n) time. Use lo + (hi - lo) / 2 to avoid integer overflow on huge arrays — a real bug fixed in the JDK in 2006.

Switch tabs to compare the same algorithm across languages, then use the visualizer to step through pointer movements one frame at a time.

Sample output when you run the program:

Index of 9  = 4
Index of 10 = -1

Walk-through: all four implementations follow the same algorithmic skeleton — only the syntax differs. Replay the visualizer to see exactly how the pointers move and which cells change; that mental movie is what interviewers expect you to narrate on a whiteboard, regardless of the language you choose.

public class BinarySearch {
    public static int search(int[] a, int target) {
        int lo = 0, hi = a.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (a[mid] == target) return mid;
            if (a[mid] < target) lo = mid + 1;
            else hi = mid - 1;
        }
        return -1;
    }
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13};
        System.out.println("Index of 9  = " + search(arr, 9));
        System.out.println("Index of 10 = " + search(arr, 10));
    }
}

Real-world use

In production, Binary Search shows up in pagination engines, search systems, recommendation feeds, log processors and analytics pipelines. Companies like Google, Meta, Amazon, Stripe and Uber rely on these exact algorithm patterns every millisecond — billions of times per day. Mastering this lesson directly improves the code you ship to real users.

Best practices

• Always state time and space complexity before writing code in an interview.
• Verify edge cases first: empty array, single element, all duplicates, all sorted, all reversed.
• Prefer in-place operations when memory is constrained, but never sacrifice readability for it.
• Add at least one test for the boundary indices (0 and n-1) before submitting.

Common mistakes

• Off-by-one errors at loop bounds — re-check < vs ≤.
• Integer overflow on sum/product problems — use long or BigInt when needed.
• Mutating the array while iterating it — copy first or iterate by index backwards.

Hands-on exercise

Interview preparation — practice these questions:

• Q1. Explain Binary Search in one sentence.
• Q2. What is the time and space complexity of Binary Search?
• Q3. Give a real-world scenario where you would use it.
• Q4. Walk through it on input [3,1,4,1,5,9,2,6].
• Q5. How does it behave on an empty array? On an array of size 1?
• Q6. How would you optimize it further if input size is 10⁸?
• Q7. Name two common bugs engineers make with this technique.