Jump to section
Binary search finds a target in a sorted array by repeatedly checking the middle element and discarding the half that cannot contain the target. Keep two bounds, low and high, and stop when they cross. It runs in O(log n) time and O(1) space, and the main risk is off-by-one errors in the bounds.
The Binary Search Problem
You are given an array of integers sorted in ascending order and a target value. Return the index of the target if it is in the array, or -1 if it is not. The solution must be faster than checking every element, which is why interviewers expect O(log n).
Example 1
Input: nums = [-1, 0, 3, 5, 9, 12], target = 9
Output: 4
Why: the middle checks go 3, then 9, which is found at index 4.
Example 2
Input: nums = [-1, 0, 3, 5, 9, 12], target = 2
Output: -1
Why: the search narrows to the gap between 0 and 3, the bounds cross, and 2 is not there.
Assumptions to confirm
- Is the array sorted ascending? (Binary search depends on it.)
- Are there duplicates? (If so, ask whether any index will do, or the first or last occurrence.)
- Can the array be empty? (Return -1.)
Start With the Brute Force
A linear scan checks each element in turn and returns the index when it finds the target. It is O(n) time and O(1) space, and it ignores the fact that the array is sorted.
Say it, then use the sorted order: if the middle element is smaller than the target, everything to its left is smaller too, so you can discard that whole half in one comparison. Halving the search space each step gives O(log n), which for a million elements is about 20 checks instead of a million.
Ready to put this into practice?
Practice this with MockIF →Still applying for jobs? Let Auto Apply do it
The Optimal Approach: Halve the Search Space
Set low = 0 and high = length - 1
Both bounds are inclusive: the target, if present, is always between them.
Loop while low <= high
With inclusive bounds, low equal to high is still a one-element range worth checking.
Take the middle safely
mid = low + (high - low) // 2 avoids overflow in languages with fixed-size integers, and it is a good habit to show.
Compare and discard half
If nums[mid] equals the target, return mid. If it is smaller, set low = mid + 1. If larger, set high = mid - 1. The +1 and -1 are what guarantee progress.
Return -1 when the bounds cross
low > high means the range is empty and the target is not in the array.
Binary Search in Python and TypeScript
One consistent convention, inclusive bounds on both ends, is the easiest way to avoid off-by-one bugs. Pick it and say it out loud.
Python
def binary_search(nums: list[int], target: int) -> int:
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if nums[mid] == target:
return mid
if nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1TypeScript
function binarySearch(nums: number[], target: number): number {
let lo = 0;
let hi = nums.length - 1;
while (lo <= hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (nums[mid] === target) return mid;
if (nums[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}Ready to put this into practice?
Practice this with MockIF →Still applying for jobs? Let Auto Apply do it
Time and Space Complexity
| Approach | Time | Space | When to use it |
|---|---|---|---|
| Linear scan | O(n) | O(1) | Unsorted data |
| Recursive binary search | O(log n) | O(log n) call stack | If asked for recursion |
| Iterative binary search | O(log n) | O(1) | The expected interview answer |
How to Talk Through It in an Interview
- Clarify: "Sorted ascending? Any duplicates, and if so which index do you want? Can it be empty?"
- Brute force: "A linear scan is O(n), but it ignores the sorted order."
- Optimise: "Because it is sorted, one comparison with the middle tells me which half to throw away, so it is O(log n)."
- Code: state your convention: "low and high are inclusive, so I loop while low is less than or equal to high, and move past mid on each side."
- Test: a target at the first index, at the last index, in the middle, missing, and an empty array. These are exactly where off-by-one bugs show up.
Ready to put this into practice?
Practice this with MockIF →Still applying for jobs? Let Auto Apply do it
Edge Cases and Common Follow-Ups
Infinite loops
Writing low = mid instead of mid + 1 with inclusive bounds can loop forever on a two-element range. Always move past mid.
First or last occurrence
When you find the target, record the index and keep searching left (or right) instead of returning, to find the boundary.
Insert position
Return low instead of -1 at the end: it is where the target would go to keep the array sorted.
Rotated sorted array
One half is always sorted. Check whether the target falls inside the sorted half to decide which way to go.
Binary search on the answer
Many problems, such as the smallest capacity that meets a deadline, search over possible answers with a yes or no check instead of over an array.
Practise binary search in a Mock Coding Round
Reading a solution is not the same as producing one with someone listening. The gap shows up as long silences, a jump straight to code without a brute force, or a bug you only spot after the interviewer asks you to test. The fix is to rehearse problems like binary search out loud, under time pressure, while explaining each decision.
MockIF runs mock coding interviews with a voice AI interviewer in a real in-browser editor, in Python and TypeScript. It runs your code against tests, asks you to explain your approach, adds follow-up questions the way a real interviewer would, and then scores your answer and gives specific feedback. Each session costs 2 credits. It is free to start with 5 credits, then monthly or 3-monthly plans, or one-off credit packs (see pricing).
Frequently Asked Questions
What is the time complexity of binary search?
Why use low + (high - low) / 2 instead of (low + high) / 2?
Should the loop be while low < high or low <= high?
Does binary search work on unsorted arrays?
How do I find the first occurrence of a duplicate value?
Stop Preparing in Your Head. Start Practicing Out Loud.
Drop your resume, add a job description, and get a mock interview like the real thing.
Start Free Mock Interview →Still applying for jobs? Let Auto Apply do it for you.