Insert into a Sorted List

Insert a number into its correct position in a sorted list using binary search.

lists binary-search insertion

Write a function `insert_sorted(nums: list[int], val: int) -> list[int]` that takes a list of integers `nums` sorted in ascending order and an integer `val`. The function should insert `val` into the list at the correct position to maintain the sorted order, and return the new list. Use binary search to find the appropriate index (do not use list.insert() with a linear scan or sorted() to solve). The original list should not be modified; return a new list. If `val` is equal to an existing element, insert it after any existing equal elements (i.e., to the right).

Constraints

0 <= len(nums) <= 1000
-1000 <= nums[i], val <= 1000
The list is sorted in non-decreasing order.

Example

>>> insert_sorted([1, 2, 4], 3)
[1, 2, 3, 4]
>>> insert_sorted([1, 2, 4], 0)
[0, 1, 2, 4]
>>> insert_sorted([1, 2, 4], 5)
[1, 2, 4, 5]
>>> insert_sorted([], 3)
[3]

10 points ~10 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Use binary search to find the first index where nums[i] > val, or len(nums) if none.

Once you have the index, create a new list by concatenating slices: nums[:idx] + [val] + nums[idx:].

Remember to handle empty lists and duplicates (insert after equal elements).

Test Results

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