Search insert position

Baseline Binary Search · 1D Arrays O(log n) · O(1)

Slotting a Job Into the Duration Ledger

A batch scheduler keeps pending jobs in a ledger sorted by estimated duration and a new job has just arrived. The dispatcher either finds the ledger entry matching the new job's duration or determines which slot it would occupy so the ledger stays sorted after insertion. Report that position.

Input: An array nums of n distinct integers sorted in ascending order, and an integer target.

Output: The index of target if present, otherwise the index where target should be inserted to keep nums sorted.

Constraints

1 <= n <= 10^4
-10^4 <= nums[i] <= 10^4
nums contains distinct values sorted in ascending order
An O(log n) algorithm is required

Examples

Example 1

Input: {"nums":[1,3,5,6],"target":5}
Output: 2
The job duration 5 already occupies slot 2, so the dispatcher reports that index directly.

Example 2

Input: {"nums":[1,3,5,6],"target":2}
Output: 1
Duration 2 lands between 1 and 3, so it would be inserted at index 1.

Solve this in your browser →

Also on LeetCode ↗