Skip to main content

26. Binary Search

easyAsked at Tesla

Locate a target in a sorted array in O(log n) — Tesla applies binary search in firmware to locate the calibration threshold entry for a given temperature bin within a sorted lookup table used by the battery management system.

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

Problem

Given a sorted array of distinct integers nums and a target value, return the index of the target. If the target is not found, return -1. You must write an algorithm with O(log n) runtime.

Constraints

  • 1 <= nums.length <= 10^4
  • -10^4 < nums[i], target < 10^4
  • All values in nums are unique and sorted in ascending order

Examples

Example 1

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

Explanation: 9 is at index 4.

Example 2

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

Approaches

1. Linear scan

Scan every element until the target is found or the array is exhausted. O(n) — violates the O(log n) requirement but useful for establishing correctness first.

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:

2. Iterative binary search

Maintain left/right pointers; compare mid to target and halve the search space each iteration. Off-by-one bugs are the main failure mode — pin the invariant: left <= right.

Time
O(log n)
Space
O(1)
function search(nums, target) {
  let left = 0, 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:

Tesla-specific tips

Tesla embeds lookup tables in battery and thermal firmware that can have thousands of entries; binary search is the standard access pattern. Interviewers use this to check loop-invariant discipline — specifically, can you explain why mid = left + (right-left)/2 instead of (left+right)/2 avoids integer overflow? Also note that using left <= right (not left < right) is the canonical form when the target can sit at any index including right. Expect a follow-up on search in a rotated sorted array (LC 33).

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →