Binary search finds a value in a sorted array by repeatedly checking the middle of the part still in play. Because the array is sorted, one comparison with the middle value tells you which half the target must be in — so the other half is thrown away without looking at it. Halving again and again, a billion values shrink to one in about 30 steps.
low = 0 and high = n - 1.low <= high, look at the middle index mid.nums[mid] is the target, return mid.nums[mid] is smaller than the target, the target can only be to its right: low = mid + 1.high = mid - 1.low > high), nothing is left in play: the target isn't there. Return -1.Members only · free account
The rest of this lesson, with 6 more sections, 1 drawing, a dry-run simulator and code in JavaScript, Python, Java and C++, opens with a free account.
Not ready yet? The Arrays course is free to read, no account needed.
In the rest of this lesson