1 · Model, solve and test · 25 MIN

Locate insertion boundaries with bisect

Locate insertion boundaries with bisect

bisect_left finds the first position at which a value could be inserted while maintaining sorted order. bisect_right places it after equal values. Their difference therefore counts occurrences without scanning the whole equal run. The list must already be sorted, and searching does not mutate it. Inserting at the returned position is a separate operation with linear movement cost for a Python list; a logarithmic search does not make the full insertion logarithmic.

Use left and right boundaries as a half-open interval of equal values.

Read the example

from bisect import bisect_left, bisect_right
def solve(input):
    left = bisect_left(input["values"], input["target"])
    right = bisect_right(input["values"], input["target"])
    return [left, right, right - left]
import json
print(json.dumps(solve(json.loads("{\"values\":[1,2,2,2,4],\"target\":2}")), separators=(",", ":")))

[1,4,3]

Your challenge

Input is {values:ascending integer list,target:int}. Return [first insertion index, index after equal values, occurrence count].

Solution cost: O(log n) comparisons. time · O(1) boundary values. space

Common trap

A logarithmic lookup followed by list insertion still incurs linear shifting.