704. Binary Search
easyAsked at IntelImplement classical binary search on a sorted integer array. Intel uses this to grade whether you write the loop with `lo + (hi - lo) / 2` (overflow-safe) rather than the textbook `(lo + hi) / 2`. The 2006 JDK bug that hid in Arrays.binarySearch for nine years is the lore every senior IC has internalized.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Intel loops.
- Glassdoor (2026-Q1)— Intel SWE phone-screen reports cite binary-search as a foundational warm-up.
- GeeksforGeeks (2025-08)— Intel Interview Experience archives list binary-search with the overflow-safe mid formula.
- LeetCode discuss (2025-11)— Intel-tagged in the LC company-frequency filter.
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-10^4 < nums[i], target < 10^4All 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-1Approaches
1. Linear scan (brute)
Walk the array; return the first index where nums[i] === target.
- 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: Throws away the sorted precondition. The problem statement explicitly requires O(log n) so this fails the rubric even if it passes the unit tests.
2. Iterative binary search (optimal)
Maintain [lo, hi] inclusive. Compute mid via lo + (hi-lo)/2 (overflow-safe). Compare nums[mid] to target; narrow the window.
- Time
- O(log n)
- Space
- O(1)
function search(nums, target) {
let lo = 0, 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: Logarithmic, constant space, branch-friendly. The `lo + (hi - lo) / 2` mid formula avoids the (lo + hi) overflow that bit Java's stdlib for nine years. In JS the issue is academic (numbers go to 2^53), but Intel writes lots of C — the habit must transfer.
Intel-specific tips
Intel will absolutely catch a `(lo + hi) / 2` mid formula and ask 'what if lo and hi are both near INT_MAX?'. Naming the 2006 JDK Arrays.binarySearch bug (where this same formula caused overflow for arrays > 2^30 elements) shows you've read Josh Bloch's blog post 'Nearly All Binary Searches and Mergesorts are Broken' — that's the Intel-flavored stdlib-history awareness.
Common mistakes
- Using `(lo + hi) / 2` instead of `lo + (hi - lo) / 2` — overflows in C/C++ for large arrays. Doesn't bite in JS but signals lack of awareness.
- Loop condition `while (lo < hi)` instead of `while (lo <= hi)` — for the inclusive-window version, the strict-less-than misses single-element windows.
- Updating with `lo = mid` or `hi = mid` (instead of mid+1, mid-1) — causes infinite loops in odd-length windows.
- Returning the wrong sentinel — the problem wants -1 for not-found, not undefined or null.
Follow-up questions
An interviewer at Intel may pivot to one of these next:
- Search Insert Position (LC 35) — return the index where target should be inserted.
- First Bad Version (LC 278) — binary search with an API call instead of array access.
- Find First and Last Position of Element in Sorted Array (LC 34) — two binary searches for lower and upper bound.
- Search in Rotated Sorted Array (LC 33) — binary search with a twist.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why is `lo + (hi - lo) / 2` overflow-safe?
`(lo + hi)` can exceed INT_MAX when both are large (in C/C++). `(hi - lo)` is bounded by the array length, which fits well within INT_MAX, so adding it to lo never overflows. Same mid value, no overflow.
Should I use iterative or recursive?
Iterative. Constant stack space, easier for the compiler to optimize, no recursion overhead. The recursive version has the same Big-O but uses O(log n) stack space, which is fine but unnecessary.
Free learning resources
Curated free links for this problem.