EasyArrayBinary Search

Search Insert Position

2 approaches, code in every language

You are given an array of distinct integers sorted in ascending order along with a target value. If the target already lives in the array, return the index where it sits. If it is absent, return the index it would occupy if it were dropped into the array while keeping everything in order.

The interesting part of this task is the runtime bound: the search has to finish in logarithmic time, so a plain left-to-right scan is off the table for the intended solution and a halving strategy is expected instead.

Example 1

Input: nums = [1,3,5,6], target = 5

Output: 2

The value 5 is already present at index 2.

Example 2

Input: nums = [1,3,5,6], target = 2

Output: 1

2 belongs between 1 and 3, so it would slot in at index 1.

Constraints

1 ≤ nums.length ≤ 10^4
-10^4 ≤ nums[i] ≤ 10^4
nums is sorted in strictly ascending order with no duplicates
-10^4 ≤ target ≤ 10^4

Linear Scan

Walk the array from the front and stop at the first element that is not smaller than the target.

Loading animation…

Intuition

Because the array is sorted, the answer is simply the position of the first element that reaches or exceeds the target. If we never find such an element, every value is smaller than the target, so the insertion point is the very end of the array. This is the most direct reading of the problem, even though it costs linear time.

Algorithm walkthrough

1Iterate over the array while tracking the current index.
2As soon as an element is greater than or equal to the target, return that index.
3If the loop finishes without returning, no element was large enough.
4Return the array length, which is the position just past the last element.

Implementation

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        for i, x in enumerate(nums):
            if x >= target:
                return i
        return len(nums)

Time

O(n)

Space

O(1)

Correct but does not meet the logarithmic-time expectation.

Binary Search (Lower Bound)

Keep a half-open window and shrink it until it collapses onto the first index whose value is at least the target.

Loading animation…

Intuition

The insertion point is exactly the lower bound: the leftmost index whose value is not less than the target. Maintaining a window [lo, hi) where hi starts one past the array lets the search collapse naturally onto that boundary, and when target is bigger than everything the window slides all the way to the end, which is the correct insertion index.

Algorithm walkthrough

1Set lo to 0 and hi to the array length, treating the window as half-open.
2While lo is less than hi, compute the midpoint.
3If the middle value is smaller than the target, move lo past the midpoint.
4Otherwise pull hi down to the midpoint since the answer is at or before it.
5When the window empties, lo is the lower bound and the answer.

Implementation

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        lo, hi = 0, len(nums)
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] < target:
                lo = mid + 1
            else:
                hi = mid
        return lo

Time

O(log n)

Space

O(1)

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Binary Search

After the pattern

Now solve one you haven't seen.

Threshold Insert Slot is our own problem on the technique behind Search Insert Position: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free