np.searchsorted finds where values belong in a sorted array with binary search. Compute both sides for several values.
What to build
A program that prints searchsorted positions for side="left" and side="right".
Requirements
- Print
leftfollowed by the left positions of all the queries, thenrightfollowed by the right positions, each list in NumPy's 1-D format. - The left position is the number of array elements smaller than the query; the right position is the number smaller than or equal to it.
Input
Line 1: the sorted array. Line 2: the query values.
Output
Two lines.
Constraints
1 to 10⁵ array elements in ascending order; 1 to 1000 queries.
Example
Input:
1 2 2 3
2 0 4
Output:
left [1 0 4]
right [3 0 4]
Why it works
Binary search halves the candidate range at every step, so each query needs only about log₂ n comparisons, and the strict or non-strict comparison decides whether equal values are counted before the position.
Examples
1 2 2 3 2 0 4
left [1 0 4] right [3 0 4]
10 20 30 25 10
left [2 0] right [2 1]
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Write a binary search: keep a range lo to hi and halve it until it is empty.
Hint 2
For side left, move right while a[mid] < v; for side right, while a[mid] <= v.
Hint 3
The bisect module does the same, but try writing the loop yourself.
Solution
Show one correct solution (try it yourself first)
def fmt(values):
w = max(len(str(v)) for v in values)
return "[" + " ".join(str(v).rjust(w) for v in values) + "]"
def search(a, v, right):
lo, hi = 0, len(a)
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < v or (right and a[mid] == v):
lo = mid + 1
else:
hi = mid
return lo
a = [int(x) for x in input().split()]
qs = [int(x) for x in input().split()]
print("left", fmt([search(a, v, False) for v in qs]))
print("right", fmt([search(a, v, True) for v in qs]))