Lesson 12.2
If the list is sorted, you can search twice as fast: look at the middle and throw away half.
def binary_search(numbers, target):
left, right = 0, len(numbers) - 1
while left <= right:
mid = (left + right) // 2
if numbers[mid] == target:
return mid
elif numbers[mid] < target:
left = ... # the right half
else:
right = ... # the left half
return -1
left and right are the bounds of the piece where the answer may still be;// is whole division: an index is never a decimal;left = mid + 1 and right = mid - 1 throw away a half; without the +1 and -1
the loop would never end;The check gives a sorted list numbers and the number target.
Write binary_search and print the index it finds, or -1.
Keep two bounds of the piece where the answer may still be, and halve it.
The middle is (left + right) // 2: whole division, an index is never a decimal.
The bounds must move by mid + 1 and mid - 1, otherwise the loop never ends.
The loop runs while left <= right.