Skip to main content

704. Binary Search

easyAsked at Intel

Implement 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 Alex Chen, 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^4
  • All the integers in nums are unique.
  • nums is sorted in ascending order.

Examples

Example 1

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

Explanation: 9 exists in nums and its index is 4.

Example 2

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

Approaches

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.

Output

Press Run or Cmd+Enter to execute

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.

Practice these live with InterviewChamp.AI

Drill Binary Search and other Intel interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →