DSA interview question

Binary Search (Search X in a Sorted Array)

Easy · Algorithms · Topics: binary search, array

The problem

A dictionary app stores a million words in sorted order and needs to check whether a typed word exists, instantly, on every keystroke. Scanning the list is O(n); binary search looks at the middle element, discards the half that can't contain the target, and repeats, so it needs about 20 comparisons for a million entries. It's simple to describe but famously easy to get wrong (Jon Bentley found most professional programmers' versions had bugs), usually through off-by-one boundaries or an overflowing midpoint.

Example: [-1, 0, 3, 5, 9, 12], target 9 → index 4.

Function signature

int binarySearch(const vector<int>& a, int target);  // index of target in sorted, distinct a, or -1

Test cases

Input `(a, target)`	Output	Explanation
`([-1, 0, 3, 5, 9, 12], 9)`	4
`([-1, 0, 3, 5, 9, 12], 2)`	-1	Not present
`([5], 5)`	0
`([5], -5)`	-1
`([1, 2, 3, 4, 5, 6, 7, 8], 1)`	0	First element
`([1, 2, 3, 4, 5, 6, 7, 8], 8)`	7	Last element
`([], 1)`	-1	Empty array

(Confirm: the array is sorted in increasing order with distinct values.)

How interviewers phrase it

"Implement binary search" (LeetCode 704).
Often a warm-up before lower/upper bound, rotated arrays, or "binary search on the answer".
"Write it iteratively and recursively."

Clarifying questions to ask

Is the array sorted? Ascending?
Are there duplicates? (If so, which occurrence to return?)
What should be returned when the target is absent?

Follow-ups to expect

"Why lo + (hi − lo) / 2 instead of (lo + hi) / 2?"
"What's the loop invariant?"
"Why lo <= hi and not lo < hi?"
"How many comparisons in the worst case?"
"Recursive vs iterative?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview