Show problems as
Classic problem #35EasyArrayBinary Search

Search Insert Position

Real-world version: Threshold Insert Slot
Tracked in this browser only
Read Search Insert Position on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstBasic Binary Search · Binary Search, animated step by step

An alerting service keeps its trigger levels in thresholds, an array of distinct integers held in increasing order. Slots are numbered from 0.

An operator wants to add the trigger level level. Report where it belongs:

  • if level is already one of the stored trigger levels, report the slot it currently occupies;
  • otherwise report the slot level would occupy after being inserted, with every later trigger level shifting one slot along so the array stays in increasing order. A level above every stored trigger level therefore belongs at slot thresholds.length.

Scanning the array end to end is too slow for the service. Your routine has to finish in time logarithmic in the length of thresholds.

Examples

Example 1

Input
thresholds = [-40, -12, 5, 18, 63], level = 18
Output
3

The level 18 is already stored at slot 3, so that slot is reported.

Example 2

Input
thresholds = [-40, -12, 5, 18, 63], level = 6
Output
3

Inserting 6 pushes 18 and 63 one slot along, so 6 lands at slot 3.

Example 3

Input
thresholds = [-40, -12, 5, 18, 63], level = 90
Output
5

Every stored level is below 90, so it is appended one past the last slot.

Constraints

  • 1 <= thresholds.length <= 10^4
  • -10^4 <= thresholds[i] <= 10^4
  • thresholds holds distinct integers in increasing order
  • -10^4 <= level <= 10^4

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def insert_slot(thresholds: list[int], level: int) -> int:
Java
public int insertSlot(int[] thresholds, int level)

More on the same topics