NumPy: searchsorted, left and right

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 left followed by the left positions of all the queries, then right followed 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

Example 1 · Input
1 2 2 3
2 0 4
Expected output
left [1 0 4]
right [3 0 4]
Example 2 · Input
10 20 30
25 10
Expected output
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]))

Lesson: Sorting, unique values and searching →