Skip to main content

704. Binary Search

easyAsked at IBM

Binary 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 Alex Chen, 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 <= 9999
  • 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

Explanation: 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.

Output

Press Run or Cmd+Enter to execute

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.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →