Skip to main content

24. Binary Search

easyAsked at Apple

Search a sorted array in O(log n) — Apple tests binary search as a stand-alone problem because getting the boundary conditions exactly right mirrors the precision required when indexing sorted Core Data fetch results or bisecting version ranges in Software Update.

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

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 values 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

Iterate through the array and compare each element. Ignores the sorted property.

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. Binary search (iterative)

Maintain lo/hi pointers. Compare midpoint to target; eliminate half each iteration. Use lo + Math.floor((hi-lo)/2) to avoid integer overflow.

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:

Apple-specific tips

Apple interviewers are known to specifically ask 'why lo + (hi - lo) / 2 instead of (lo + hi) / 2?' — the answer (overflow prevention on 32-bit signed integers) is a systems-awareness test. Off-by-one on the loop condition (< vs <=) is the most common failure; slow down and articulate your loop invariant. Apple's darwin kernel and XNU use bisection for sorted lookup tables — mentioning this real-world grounding scores points.

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 Apple interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →