Skip to main content

92. Binary Search

easyAsked at Workday

Implement binary search on a sorted array. Workday uses this as a fluency check — they'll follow up with rotated-search and first-bad-version variants in the same interview.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2025)— Workday SDE1 phone screen.

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

Example 2

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

Approaches

1. Linear search

Walk and compare.

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

Tradeoff: Violates O(log n).

2. Iterative binary search

Standard textbook binary search.

Time
O(log n)
Space
O(1)
function search(nums, target) {
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >>> 1;
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

Tradeoff: Closed interval [lo, hi]. Use >>> 1 for overflow safety in non-JS languages.

Workday-specific tips

Workday wants the standard closed-interval [lo, hi] template. Articulate the invariant: 'if target exists, it lies in [lo, hi]'. Use (lo + hi) >>> 1 for overflow safety in mixed-language conversations.

Common mistakes

  • Using < instead of <= in the loop condition — misses the case lo == hi.
  • Updating lo = mid (not mid + 1) — infinite loop when target > all elements.
  • Wrong arithmetic — (lo + hi) / 2 vs Math.floor((lo+hi)/2).

Follow-up questions

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

  • Search Insert Position (LC 35) — lower bound.
  • First Bad Version (LC 278).
  • Find First and Last Position (LC 34).

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

Closed interval [lo, hi]. When lo == hi, we haven't yet checked that single index. Strict < would skip it.

Half-open vs closed?

Both work. Half-open [lo, hi) is preferred for lower-bound variants because the answer can be N. Closed is shorter for exact-match search.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →