Skip to main content

704. Binary Search

easyAsked at Anduril

Search a sorted array for a target value in O(log n) time. Anduril asks this to verify you can implement binary search bug-free — off-by-one errors in loop invariants are a classic source of hard-to-reproduce bugs in firmware, and they watch for them carefully.

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

Source citations

Public interview reports confirming this problem appears in Anduril loops.

  • Glassdoor (2025-12)— Cited in Anduril SWE screening threads as a baseline divide-and-conquer sanity check.
  • Blind (2025-08)— Anduril candidates mention binary search as a fundamental test for loop-invariant clarity in early rounds.

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 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. Iterative binary search

Maintain left and right pointers. At each step, check the midpoint and halve the search space based on the comparison.

Time
O(log n)
Space
O(1)
function search(nums, target) {
  let left = 0;
  let right = nums.length - 1;
  while (left <= right) {
    // Use (left + right) >>> 1 to avoid integer overflow in languages like C++/Java
    const mid = left + Math.floor((right - left) / 2);
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) {
      left = mid + 1; // target is in the right half
    } else {
      right = mid - 1; // target is in the left half
    }
  }
  return -1;
}

Tradeoff: The canonical O(log n) iterative implementation. Using (right - left) / 2 + left instead of (left + right) / 2 prevents integer overflow — important in C++ and Java; mention it anyway at Anduril as it signals cross-language awareness.

2. Recursive binary search

Same logic expressed recursively. Slightly cleaner to read but uses O(log n) call-stack space.

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

Tradeoff: O(log n) stack space. Fine for most contexts, but iterative is preferred in embedded environments where call-stack depth is bounded and predictable.

Anduril-specific tips

State the loop invariant explicitly: 'At every step, if target exists in nums, it lies within [left, right].' Anduril interviewers pay close attention to the boundary conditions — left <= right vs left < right, and mid+1 vs mid. Mention overflow-safe midpoint computation even in JavaScript; it demonstrates that you think about cross-platform and cross-language correctness, which matters at a company that ships C++ and Rust in production.

Common mistakes

  • Using left < right instead of left <= right — this misses the single-element case where left == right == the target index.
  • Setting right = mid instead of right = mid - 1 — can cause an infinite loop when left == mid.
  • Computing mid = (left + right) / 2 without the overflow-safe form — not a JS issue but a correctness concern in C++/Java.
  • Forgetting to return -1 — if the while loop exits without finding the target, that's a miss.

Follow-up questions

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

  • Find the first or last occurrence of a target in a sorted array with duplicates.
  • Search in rotated sorted array (LC 33) — requires determining which half is sorted.
  • Binary search on the answer space — e.g., minimize the maximum value (LC 875, LC 1011).

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 is still one element to check. Using < instead of <= would skip it.

Why mid + 1 and mid - 1 instead of mid?

Because we already checked mid and it wasn't the target. If we used right = mid, we'd check mid again indefinitely when left == mid.

Does JavaScript have integer overflow?

Not for numbers in the safe integer range, but (left + right) / 2 is still better practice and shows awareness of C++/Java behavior where Anduril's embedded code actually runs.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →