Search Insert Position

Easy · binary-search insert index. Real solution for this problem — same player as the hand-authored deep-dives.

Problem

Read the prompt, flip through the examples, then steal the idea.

LeetCode 35. Search Insert Position. The copyrighted prompt is on LeetCode. This page is a working binary-search insert index for this problem: editable input, Python, Go, and a step-by-step animation.

Constraints

—Player inputs are capped so the animation stays readable.
—Match LeetCode's own constraints when you submit there.

Examples

Input

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

Output

Solution

Python and Go. The walkthrough below runs this same code.

Approach 1Optimal▶ Animated

Binary search for the lower bound

Find the first index where nums[i] >= target. That is the found index, or where target would be inserted.

Same halving as binary search. When the range collapses, lo is the insertion point — including n when the target is larger than every value.

Algorithm

While lo < hi, probe mid.
If nums[mid] < target, search the right half; else search the left (keeping mid).
Return lo.

Time: O(log n)
Space: O(1)

Solution.py

1class Solution:2    def searchInsert(self, nums: list[int], target: int) -> int:3        lo, hi = 0, len(nums)4        while lo < hi:5            mid = (lo + hi) // 26            if nums[mid] < target:7                lo = mid + 18            else:9                hi = mid10        return lo

Watch this run

Interactive walkthrough

Playing “Binary search for the lower bound”. Edit the input, hit Run, then scrub.

Approach: Binary search for the lower bound

Loading animation…