Off by one
Read · 1 of 2
Where loops start and stop
Most bugs in loops are off by one: stopping one step early (< instead of <=) or starting one too late.
Test the boundaries directly: a list of one item, the target at the very start, at the very end.
Read this lesson as text
< or <=, n or n − 1: the most common bug there is.
Where loops start and stop
Most bugs in loops are off by one: stopping one step early (< instead of <=) or starting one too late.
Test the boundaries directly: a list of one item, the target at the very start, at the very end.
Break it: Break the binary search
This binary search should print the position of target in the sorted list (all numbers different), or -1 if it's not there. Find an input where it's wrong.
n = int(input())
nums = list(map(int, input().split()))
target = int(input())
lo, hi = 0, n - 1
found = -1
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] == target:
found = mid
break
elif nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
print(found)Input rules: line 1 n (1 to 20), line 2 n different whole numbers in increasing order (-1000 to 1000), line 3 the target.