704. Binary Search
easyAsked at IBMBinary Search is IBM's correctness screener — the interviewer is grading whether you can write a bug-free binary search on the whiteboard, handle the overflow-safe midpoint, and articulate the loop-invariant. Surprisingly few candidates ship this on the first attempt.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in IBM loops.
- Glassdoor (2026-Q1)— IBM SWE-1 and Watson new-grad recurring screener.
- LeetCode (2026-Q1)— Top-30 IBM-tagged problem.
- GeeksforGeeks (2025-12)— Listed in IBM interview-experience archive.
Problem
Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1. You must write an algorithm with O(log n) runtime complexity.
Constraints
1 <= nums.length <= 10^4-9999 <= nums[i], target <= 9999All the integers in nums are unique.nums is sorted in ascending order.
Examples
Example 1
nums = [-1,0,3,5,9,12], target = 94Explanation: 9 exists in nums and its index is 4.
Example 2
nums = [-1,0,3,5,9,12], target = 2-1Explanation: 2 does not exist in nums so return -1.
Approaches
1. Linear scan (rejected baseline)
Walk the array element by element.
- Time
- O(n)
- Space
- O(1)
function searchLinear(nums, target) {
for (let i = 0; i < nums.length; i++) {
if (nums[i] === target) return i;
}
return -1;
}Tradeoff: Trivially correct but violates the O(log n) requirement. Mention it only to dismiss it — coding it is a waste of board time.
2. Iterative binary search (optimal)
Two pointers lo/hi, narrow the window by half each iteration. Overflow-safe midpoint.
- Time
- O(log n)
- Space
- O(1)
function search(nums, target) {
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;
}Tradeoff: O(log n) and O(1) space. The two critical bugs to avoid are: (1) `(lo + hi) / 2` integer overflow on languages with fixed-width ints — use `lo + (hi - lo) / 2`; (2) inclusive `lo <= hi` vs exclusive — pick one convention and be consistent.
3. Recursive binary search
Same logic, expressed recursively.
- Time
- O(log n)
- Space
- O(log n) call stack
function searchRecursive(nums, target, lo = 0, hi = nums.length - 1) {
if (lo > hi) return -1;
const mid = lo + Math.floor((hi - lo) / 2);
if (nums[mid] === target) return mid;
if (nums[mid] < target) return searchRecursive(nums, target, mid + 1, hi);
return searchRecursive(nums, target, lo, mid - 1);
}Tradeoff: Cleaner to derive but O(log n) stack space. Iterative is preferred in production. Show this only if the interviewer asks for an alternative.
IBM-specific tips
IBM is famously strict on binary-search correctness — public reports cite multiple candidates who failed an onsite because they shipped an off-by-one or an infinite loop. Three rules that save points: (1) overflow-safe midpoint (`lo + (hi - lo) / 2`), (2) pick a single convention (inclusive `lo <= hi` and exclusive `hi = mid - 1`) and stick with it, (3) dry-run on a 1-element and 2-element input on the whiteboard before claiming done.
Common mistakes
- Using `(lo + hi) / 2` — overflows in languages with fixed-width ints. In JS the issue is float coercion if you forget Math.floor.
- Mixing inclusive `lo <= hi` with `hi = mid` instead of `hi = mid - 1` — infinite loop.
- Returning lo (or hi) when the value isn't found instead of -1.
- Forgetting that the array is 0-indexed when reporting the result.
- Not dry-running on a 1-element array to catch the empty-window bug.
Follow-up questions
An interviewer at IBM may pivot to one of these next:
- Find First and Last Position of Element in Sorted Array (LeetCode 34).
- Search in Rotated Sorted Array (LeetCode 33).
- Find Peak Element (LeetCode 162).
- Binary search on a real-valued function (e.g. nth root).
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why does IBM still ask Binary Search in 2026?
Because most candidates fail to ship it bug-free on the first attempt. It's a 5-minute screener that filters out 'memorized solutions to harder problems' from 'can actually reason about loop invariants.' Public reports show IBM uses it heavily on SWE-1 and Watson new-grad screens.
Inclusive [lo, hi] or exclusive [lo, hi)? Which does IBM expect?
Either works — what matters is internal consistency. Inclusive (`lo <= hi`, `hi = mid - 1`) is the most common in interviews because it matches the way most people draw the pointers on a whiteboard. Pick one, state it aloud, and stick to it. Mixing them is the single biggest source of infinite loops.
Free learning resources
Curated free links for this problem.