Find the position of a target value in a sorted array, using an efficient search.
The first line contains an integer n.
The second line contains n distinct integers in strictly increasing order.
The third line contains the integer target.
The 0-based index of target in the array, or -1 if it is not present.
Example 1
5 1 3 5 7 9 7
3
7 is at index 3 (0-based).
Example 2
5 1 3 5 7 9 4
-1
4 is not in the array, so -1.
Example 3
1 42 42
0
Single element at index 0.
The array is sorted — you do not need to look at every element. Halve the search range each step.
Keep a low and high bound. Compare the middle element to the target and discard the half that cannot contain it.
Binary search: maintain [lo, hi]. Compare arr[mid] to target; move lo or hi to discard half the range each step until found or the range is empty.
import sys
data = list(map(int, sys.stdin.read().split()))
n = data[0]
arr = data[1:1 + n]
target = data[1 + n]
lo, hi, ans = 0, n - 1, -1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target:
ans = mid
break
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
print(ans)
Tell us what needs to change, who it affects and any important deadline. We will review the context and reply with useful next questions.