Skip to main content

704. Binary Search

easyAsked at Linear

Search a sorted array in O(log n). Linear asks this to verify you can write a correct binary search without off-by-one bugs — a small problem that reveals a lot about coding precision.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Linear loops.

  • Glassdoor (2025-12)— Cited as a first-round baseline problem in Linear SWE interview reports.
  • Levels.fyi (2026-Q1)— Noted as a core competency check in Linear SWE phone screen write-ups.

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, 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 at index 4.

Example 2

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

Explanation: 2 does not exist in nums.

Approaches

1. Linear scan (baseline)

Iterate through the array and return the index where nums[i] === target.

Time
O(n)
Space
O(1)
function search(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] === target) return i;
  }
  return -1;
}

Tradeoff: Trivially correct, but ignores the sorted property. The problem explicitly requires O(log n), so only use this as a setup for binary search.

2. Binary search (optimal)

Maintain a search window [left, right]. At each step, compare the midpoint with target and halve the window.

Time
O(log n)
Space
O(1)
function search(nums, target) {
  let left = 0;
  let right = nums.length - 1;
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

Tradeoff: O(log n) time, O(1) space. Two classic bugs to avoid: use left + (right-left)/2 to prevent integer overflow (critical in languages with fixed-width ints), and use <= not < in the while condition.

Linear-specific tips

Linear uses this problem to check coding precision. Walk through your midpoint calculation and explicitly note why you use left + (right - left) / 2 rather than (left + right) / 2. Even in JavaScript where overflow is rare, explaining the safe form shows you understand integer semantics — a signal Linear graders watch for.

Common mistakes

  • Using (left + right) / 2 — can overflow in languages with 32-bit integers even though JavaScript avoids this.
  • Using left < right instead of left <= right — misses the case where the target is the final remaining element.
  • Forgetting to move left and right past mid (mid+1 / mid-1) — causes an infinite loop when nums[mid] !== target.

Follow-up questions

An interviewer at Linear may pivot to one of these next:

  • Search in Rotated Sorted Array (LC 33) — binary search with a twist.
  • Find First and Last Position (LC 34) — binary search for leftmost and rightmost bounds.
  • How would you binary search for the insertion position of a missing target?

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 left <= right and not left < right?

When left === right, there's exactly one candidate left to check. left < right would skip it and always return -1 for a single-element window that contains the target.

How do I find the first or last occurrence?

Don't return when you find a match — narrow the window further. For first occurrence, set right = mid - 1; for last, set left = mid + 1.

Can I do this recursively?

Yes, but iterative is preferred — no call-stack overhead, and the loop termination condition is explicit.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →