Given an array of integers nums sorted in ascending order and an integer target, return the index of target if it exists in nums, otherwise return -1. The algorithm must run in O(log n) time.
nums = [-1,0,3,5,9,12], target = 94nums = [-1,0,3,5,9,12], target = 2-1Click any number to search for it, or type one that isn't in the array.
lo = 0, hi = nums.length − 1lo ≤ hi: mid = lo + (hi − lo) / 2nums[mid] == target → return midnums[mid] < target → lo = mid + 1 (discard the left half)hi = mid − 1 (discard the right half)lo > hi) → return -1Every comparison throws away half of what's left, so the range shrinks 20 → 10 → 5 → 2 → 1. Even for 1,000,000 sorted numbers binary search needs at most 20 comparisons, while a linear scan may need a million. Use lo + (hi − lo) / 2 instead of (lo + hi) / 2 so the sum can't overflow for large indices.
Target smaller than every element, larger than every element, equal to the first or last element, and a single-element array. Try each one with the chips above: the loop always ends with either a match or an empty range.