Binary Search

Easy

Problem

Given a sorted array of distinct integers and a target, return the target's index, or −1 if it is absent, in O(log n) time.

Example 1

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

Example 2

Input:  target = 2
Output: -1

Test cases

Case 1

Input:    [-1,0,3,5,9,12], 9
Expected: 4

Case 2

Input:    [-1,0,3,5,9,12], 2
Expected: -1

Case 3

Input:    [5], 5
Expected: 0

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Closed interval [lo, hi]

Time O(log n)Space O(1)

Halve the range each step; stop when lo passes hi.

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

Pick one interval convention (closed or half-open) and use it everywhere — mixing them causes off-by-one bugs.