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.
Scanning from left to right is O(n). It ignores that the array is sorted.
Look at the middle element. If it is the target, you are done. If it is smaller, the target can only be on the right, so discard the left half. If it is bigger, discard the right half.
Compare with the middle and throw away half. Use low plus high minus low over 2 to avoid overflow.
Run the animation above on your own input, or watch the 1:08 video explanation of Binary Search with a dry run and Java code.