467. Binary Search
Your function receives an array of integers nums, sorted in ascending order with no duplicate values, and an integer target. Return the 0-based index where target sits in nums, or -1 if it is not present.
Because the values are distinct, the answer index is unique. Aim for an algorithm that runs in O(log n) time — the array being sorted is the whole point.
Example 1:
Input: nums = [-1, 0, 3, 5, 9, 12], target = 9
Output: 4
Explanation: nums[4] = 9, so the answer is index 4.
Example 2:
Input: nums = [-1, 0, 3, 5, 9, 12], target = 2
Output: -1
Explanation: 2 does not appear anywhere in the array, so the answer is -1.
Constraints:
- 1 ≤ nums.length ≤ 10⁴
- -10⁴ ≤ nums[i], target ≤ 10⁴
- All values in nums are unique and sorted in ascending order.
Hints:
Compare target with the middle element. Because the array is sorted, one comparison tells you which half of the array target could possibly live in — the other half is gone for good.
Maintain two indices lo and hi bounding the still-possible region, loop while lo <= hi, and move the boundary past mid on each miss (lo = mid + 1 or hi = mid - 1). Halving each round gives O(log n) steps; compute mid as lo + (hi - lo) / 2 to be overflow-safe in fixed-width languages.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [-1, 0, 3, 5, 9, 12], target = 9
Expected output: 4