This binary search misses some values, and can even run forever. Fix it.
What to build
A correct binary search, made by repairing the starter.
Requirements
- Find and fix the bugs in
search. - Print the position of the target, or
-1if it is not there.
Input
The first line has n. The second line has n different whole numbers in increasing order. The third line has the target.
Output
One number.
Constraints
n is from 1 to 1000.
Example
Input:
5
1 3 5 7 9
7
Output:
3
Why it works
while low <= high is needed because one remaining item must still be checked. Moving to mid + 1 or mid - 1 makes the range shrink every time, which guarantees that the loop ends.
Examples
Example 1 · Input
5 1 3 5 7 9 7
Expected output
3
Example 2 · Input
5 1 3 5 7 9 4
Expected output
-1
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Search for the first and the last item of the list.
Hint 2
Think about what happens when low and high are equal.
Hint 3
If the middle is too small, low must move past it.
Solution
Show one correct solution (try it yourself first)
def search(nums, target):
low = 0
high = len(nums) - 1
while low <= high:
mid = (low + high) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
n = int(input())
nums = [int(x) for x in input().split()]
print(search(nums, int(input())))