Find a value in a sorted list using binary search. Print its position (counting from 0), or -1 if it is not there.
What to build
A search that halves the list at every step.
Requirements
- Read the sorted list and the target.
- Print the target's position, or
-1.
Input
The first line has n (1 to 100000). The second line has n different whole numbers in increasing order. The third line has the target.
Output
The target's position, or -1.
Constraints
n is from 1 to 100000.
Example
Input:
10
2 5 8 12 16 23 38 56 72 91
23
Output:
5
Why it works
Because the list is sorted, one comparison with the middle item rules out half of what is left.
Examples
Example 1 · Input
10 2 5 8 12 16 23 38 56 72 91 23
Expected output
5
Example 2 · Input
3 1 2 3 4
Expected output
-1
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Keep low and high; look at mid = (low + high) // 2 each round.
Hint 2
If nums[mid] is too small, move low to mid + 1; if too big, move high to mid - 1.
Solution
Show one correct solution (try it yourself first)
n = int(input())
nums = [int(x) for x in input().split()]
target = int(input())
low, high = 0, n - 1
answer = -1
while low <= high:
mid = (low + high) // 2
if nums[mid] == target:
answer = mid
break
elif nums[mid] < target:
low = mid + 1
else:
high = mid - 1
print(answer)