Search Insert Position

Find the index where a target fits into a sorted list using binary search.

binary-search arrays searching

You are given a sorted list of integers `nums` (sorted in non-decreasing order) and a `target` integer. Write a function `search_insert(nums, target)` that returns the index where `target` should be inserted into `nums` to keep it sorted. If `target` already exists, return its index. 

Your solution must run in O(log n) time, where n is the length of `nums`. Do not use built-in search functions like `index()` or `bisect`.

**Input:**
- `nums`: list of integers, sorted in non-decreasing order.
- `target`: integer to search or insert.

**Output:**
- An integer index such that after inserting `target` at that index, `nums` remains sorted. If `target` is present, return the earliest index where it appears.

Constraints

- 0 <= len(nums) <= 10^4
- -10^4 <= nums[i], target <= 10^4
- The solution must have O(log n) time complexity and O(1) extra space.

Example

>>> search_insert([1, 3, 5, 6], 5)
2
>>> search_insert([1, 3, 5, 6], 2)
1
>>> search_insert([1, 3, 5, 6], 7)
4
>>> search_insert([1, 3, 5, 6], 0)
0
>>> search_insert([], 5)
0

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think binary search: maintain left and right boundaries.

When the middle element is less than the target, move left to mid+1; otherwise move right to mid.

The final left pointer gives the correct insertion index.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.