Binary Search
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
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.