📖 10 min read
Last updated on

Binary Search — Coding Interview Walkthrough

By intervu.dev

Hero Image for Binary Search

You’re in a coding interview. The interviewer says: “Given a sorted array and a target value, return the index of the target. Your solution must run in O(log n) time.” You’ve seen Binary Search before. You know the concept: split the array, compare the midpoint, discard half. But now you need to write it under pressure with zero off-by-one errors, explain why your loop condition is <= and not <, and handle the follow-up about rotated arrays. That’s a very different challenge.

This walkthrough covers how that conversation unfolds: the clarifying questions worth asking, the boundary decisions that trip up even experienced engineers, and the precise verbal framing that separates confident candidates from uncertain ones.

The Problem

Given a sorted array of distinct integers nums and a target integer target, return the index of target in the array. If target is not present, return -1. Your solution must run in O(log n) time. (LeetCode #704)

Example

Input

nums = [-1, 0, 3, 5, 9, 12], target = 9

Output

4

The value 9 appears at index 4 in the sorted array. The O(log n) constraint rules out a simple linear scan, and the interviewer is explicitly asking for the binary search approach. A second example: if target = 2, the output is -1 because 2 does not exist in the array.

Already comfortable with the solution? Practice it in a mock interview →

What Interviewers Are Actually Testing

Binary Search is a litmus test for precision. The algorithm has maybe five lines of meaningful logic, which means there’s nowhere to hide. Interviewers watch closely for whether you can implement a well-known algorithm cleanly, handle boundaries correctly, and explain your choices as you go.

SkillWhat Interviewers Observe
Algorithmic precisionDo you get the loop condition and pointer updates exactly right?
Off-by-one awarenessDo you use left <= right or left < right, and can you justify it?
Overflow preventionDo you compute mid as left + (right - left) // 2 instead of (left + right) // 2?
CommunicationDo you narrate boundary decisions or code silently and hope for the best?
Edge case handlingDo you test against empty arrays, single elements, and targets at the boundaries?
GeneralizationCan you extend this to “first/last occurrence” or “search in rotated array”?

Step 1: Clarifying Questions

Even for a well-known algorithm, asking clarifying questions before coding demonstrates discipline. Here are the most valuable ones for Binary Search:

  1. Is the array guaranteed to be sorted? The problem states it is, but confirming shows you understand that binary search’s correctness depends entirely on sorted order. In a real-world variant, this might not be guaranteed.

  2. Are all elements distinct, or can there be duplicates? This problem uses distinct integers, which simplifies things. With duplicates, “find the target” becomes ambiguous (first occurrence? any occurrence?). Knowing this helps you avoid over-engineering.

  3. Should I return the index or the value? The problem asks for the index, a detail worth confirming, since some variants return true/false or the element itself.

  4. What should I return if the target isn’t found? The problem specifies -1, but this is worth restating. Some interview variants ask you to return the insertion point instead (LeetCode #35).

  5. What are the constraints on array size? Knowing n can reach 10,000+ confirms that O(log n) is meaningful here. It also lets you calculate that at most ~14 iterations are needed for 10,000 elements, a satisfying fact to mention.

Step 2: A First (Non-Optimal) Idea

The obvious starting point is a linear scan: iterate through every element and return the index where the value matches the target.

def search(nums, target):
    for i in range(len(nums)):
        if nums[i] == target:
            return i
    return -1
ApproachTimeSpace
Linear scanO(n)O(1)

This is correct, and for small arrays it’s perfectly reasonable. But the problem explicitly requires O(log n), and the interviewer has told you the array is sorted, which is a strong hint that you’re expected to exploit that structure.

A sorted array is a gift: it tells you that everything to the left of a given index is smaller, and everything to the right is larger. Linear search throws that information away. Binary search uses it to eliminate half the array with every comparison.

Always mention the brute force, then pivot: “Linear search works but ignores the sorted property. I can do much better by exploiting the ordering.”

Step 3: The Key Insight

A sorted array lets you make a guaranteed elimination with every comparison. Pick the middle element. If it equals the target, you’re done. If the target is less than the middle, ignore the right half. If greater, ignore the left half. Each step cuts the problem in half.

Here’s how to reason through it verbally: pick the middle element of your current search range. If it equals the target, you’re done. If the target is less than the middle element, it can only be in the left half, so you safely ignore everything to the right. If the target is greater, it can only be in the right half, so you ignore everything to the left.

Each comparison cuts the problem in half. An array of 1,000 elements needs at most 10 comparisons. An array of 1,000,000 needs at most 20. That’s the power of O(log n).

The hard part isn’t the concept. It’s the boundary conditions. Where exactly do left and right start? When does the loop end? How do you update the pointers? Getting these details right without a bug is what separates clean implementations from the “almost works” ones that fail on edge cases.

Sorted array [-1,0,3,5,9,12] with lo pointer at index 0, mid at index 2, hi at index 5. Target 9 found at index 4 (highlighted). ---

Step 4: Optimal Strategy

Here’s the algorithm, step by step:

  1. Initialize left = 0 and right = len(nums) - 1, representing the inclusive search boundaries.
  2. While left <= right (meaning there’s still at least one element to check):
  3. Compute mid = left + (right - left) // 2 to find the middle index without risking integer overflow.
  4. If nums[mid] == target, return mid. Found it.
  5. If nums[mid] < target, the target must be to the right. Set left = mid + 1.
  6. If nums[mid] > target, the target must be to the left. Set right = mid - 1.
  7. If the loop exits without finding the target, return -1.

Two decisions deserve special attention: using left <= right (not <) ensures you check arrays with a single remaining element. And updating to mid + 1 / mid - 1 (not just mid) ensures the search space actually shrinks each iteration. Without this, you can get an infinite loop.

Python Implementation

def search(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1  # Inclusive boundaries

    while left <= right:  # Continue while search space is non-empty
        # Compute mid this way to avoid integer overflow (matters in lower-level languages)
        mid = left + (right - left) // 2

        if nums[mid] == target:
            return mid                  # Found the target
        elif nums[mid] < target:
            left = mid + 1              # Target is in the right half
        else:
            right = mid - 1             # Target is in the left half

    return -1  # Target not in array

Style notes worth mentioning in an interview:

  • The mid computation using left + (right - left) // 2 instead of (left + right) // 2 prevents integer overflow. In Python this doesn’t matter, but in Java or C++ it does, and mentioning it signals real-world awareness.
  • The left <= right loop condition is deliberately inclusive. It handles the case where one element remains.
  • Each branch updates left or right past mid, not to mid, ensuring the search space strictly shrinks every iteration.

Time & Space Complexity

OperationComplexity
TimeO(log n)
SpaceO(1)

Time: Each iteration halves the search space. Starting from n elements, after k iterations you have n / 2^k elements remaining. The loop ends when n / 2^k < 1, so k = log₂(n) iterations maximum.

Space: The iterative implementation uses only three variables (left, right, mid) regardless of input size, constant space. Note: a recursive implementation uses O(log n) space due to the call stack. This is worth mentioning as a comparison point.

Common Interview Mistakes

  1. Using left < right instead of left <= right. This causes the loop to exit one iteration early, missing the case where exactly one element remains in the search space. If that single element is your target, you’ll incorrectly return -1.

  2. Setting left = mid or right = mid instead of mid ± 1. If nums[mid] != target, you need to exclude mid from the next search range. Failing to do so can create an infinite loop when left and right are adjacent.

  3. Computing mid = (left + right) // 2. Correct in Python, but a classic integer overflow bug in Java and C++. Getting in the habit of writing left + (right - left) // 2 is worth the extra keystrokes, and mentioning it earns points.

  4. Not handling an empty array. If nums = [], the loop never executes and -1 is returned correctly, but only if your initialization doesn’t cause an index error. Confirm this with your interviewer or add a guard clause.

  5. Forgetting to test boundary targets. The most common off-by-one bugs manifest when the target is the first or last element. Mentally trace nums = [1, 3, 5], target = 1 and target = 5 through your code before declaring it done.

  6. Jumping to code without explaining the loop invariant. Binary search is fundamentally about maintaining a contract: “the target, if it exists, is always within [left, right].” Candidates who explain this invariant demonstrate true understanding, not just memorization.

  7. Coding silently. With a 5-line implementation, your verbal explanation is the interview. Saying nothing while you type gives the interviewer nothing to evaluate. Narrate every decision, especially the boundary choices.

What a Strong Candidate Sounds Like

“The array is sorted and I need O(log n), so binary search is the right approach. The core idea is to maintain a search window defined by left and right pointers, and at each step check the midpoint. If the midpoint is my target, I return it. If it’s too small, I move left up past mid. If it’s too large, I move right down past mid. Either way, I eliminate half the remaining elements.

The two implementation details I’m careful about: I use left <= right as my loop condition, not left < right, so I don’t miss a single-element window. And I compute mid as left + (right - left) // 2 to avoid overflow. Not an issue in Python, but a good habit. If the loop exits without a match, I return -1.

Let me trace through the example quickly to verify before submitting.”

Example Interview Dialogue

Interviewer: Implement binary search on a sorted array.

Candidate: Sure. Just to confirm: the array is sorted, elements are distinct, and I return the index or -1 if not found?

Interviewer: Correct.

Candidate: Great. I’ll maintain two inclusive pointers, left and right, and check the midpoint each iteration. If nums[mid] is less than the target, I move left to mid + 1. Not just mid, otherwise I risk an infinite loop. Same logic for moving right down. My loop condition is left <= right so I don’t exit too early when one element remains.

Interviewer: Why not use (left + right) // 2 for the midpoint?

Candidate: In Python it doesn’t matter, but in Java or C++, left + right can overflow a 32-bit integer if both are near INT_MAX. Writing left + (right - left) // 2 gives the same result without the overflow risk. I make it a habit.

Interviewer: What if you needed to find the first occurrence of a target in an array with duplicates?

Candidate: I’d modify the “found” branch. Instead of returning immediately when nums[mid] == target, I’d record that index as a candidate answer, then continue searching the left half by setting right = mid - 1. That way I keep narrowing until I find the leftmost match.

Binary search is a template, not just an algorithm. These problems all use the same divide-and-eliminate pattern in progressively less obvious ways:

The jump from #704 to #33 is one of the most common interview progressions. If you nail the base case, be ready to explain how you’d handle a rotated array.

Practice This in a Mock Interview

Reading a Binary Search explanation is a solid start, but this problem trips up experienced engineers because of execution under pressure, not lack of knowledge. When someone is watching, the off-by-one errors you’d catch in a quiet test environment have a way of slipping through. The loop condition that seemed obvious becomes suddenly ambiguous.

The only reliable way to build confidence with precision-dependent algorithms is to code them out, repeatedly, with feedback.

Start a mock interview for Binary Search on Intervu.

Further reading:

Practice Like It's the Real Interview

Get instant feedback on your approach, communication, and code — powered by AI.

Start a Mock Interview →