DSA sheet · Binary Search · Classic binary search pattern

Search Insert Position

Third question of the classic pattern (LeetCode 35). It's Binary Search Basics with one twist: if the target is not in the array, we don't return −1. We return the index where it should go so the array stays sorted. The teacher first writes a simple linear scan, uses the constraints to explain when that stops being enough, and then writes binary search. Its only change from the basic template is the last line: return left.

Why it matters: "where would this value go?" is the idea behind lower bound, floor/ceiling, first occurrence and many later problems. The question "why left and not right?" is the first real taste of thinking about where the pointers end up.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the conditions from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · Linear scan: the first index with value ≥ target
• Part B · Binary search, return left
• Part C · Revision page

Part 0 · Before starting

Words we will use

• Index: position in the array, counted from 0. In an array of n items, the last index is n − 1.
• Insert position: if we squeeze the target into the array at index p, pushing everything from p onward one step right, the array is still sorted.
• left / right (low / high): the two ends of the part of the array we're still searching. mid: the middle index.

Why binary search works here

The array is sorted. Ask "is nums[i] >= target?" for each i. Because the array only grows, the answers look like no no no yes yes yes. They flip once. The insert position is exactly the first "yes" (or n if there is no "yes"). A yes/no that flips once is what binary search needs: at mid, the answer tells us which side the flip is on.

The mid formula

We write mid = left + (right - left) // 2. It gives the same index as (left + right) // 2. The teacher repeats the reason: in Java/C++, if right is huge, left + right can go past the int limit and become negative (overflow). Subtracting first keeps the numbers small. Python ints never overflow, so here it's just a good habit. With n ≤ 10⁴ even Java would be fine with the simple form.

Part A · Linear scan: the first index with value ≥ target

LeetCode 35

1The question in simple words

You get a sorted array of distinct integers (no repeats) and a target.

• If the target is in the array → return its index.
• If not → return the index where it would be inserted so that the array stays sorted.

target 5 → 2 (found) · target 2 → 1 (goes between 1 and 3) · target 7 → 4 (after the end) · target 0 → 0 (before everything).

2What the constraints tell us

• 1 ≤ nums.length ≤ 10⁴. The teacher always reads this first: about 10⁸ operations is where code gets too slow (TLE). 10⁴ is small, so an O(n) scan easily passes.
• Values and target are between −10⁴ and 10⁴: negatives are allowed, and the numbers are small.
• Distinct and sorted ascending. Her tip: when numbers are sorted, think of two pointers or binary search for the optimised version. For the brute force, just use plain loops.

3Intuition

Say we must insert 3 into an array that starts 1, 2, 4, … Looking at it, we know right away that 3 goes after 2 and before 4. The code doesn't "see" that, so it has to walk through the items one by one.

4Building the conditions from examples

Insert 3 into an array that starts 1 2 4 …:

• i = 0, value 1. 3 is bigger, so 3 belongs somewhere to the right. Move on.
• i = 1, value 2. Still smaller than 3. Move on.
• i = 2, value 4. Now the value is bigger than 3. We only got here because every earlier value was smaller than 3. So 3 fits right here, at index 2: before 4 and after 2.

Rule so far: the first index where nums[i] > target is the answer.

Why >= and not just >

If the target is already in the array (e.g. the value at index 2 were 3 itself), the question says return that index. So "equal" must also stop the loop and return i. The condition becomes nums[i] >= target.

What if nothing is ≥ target?

Say we insert 10 and every value is smaller. The loop finishes without returning. Where does 10 go? After the last item. The last index is n − 1, so one after it is (n − 1) + 1 = n. Return len(nums).

5Approach steps

1. For i from 0 to n − 1: if nums[i] >= target → return i.
2. After the loop → return n.

6Code (Python)

class SolutionLinear:
    def searchInsert(self, nums, target):
        n = len(nums)
        for i in range(n):
            if nums[i] >= target:   # found it, or found where it fits
                return i
        return n                    # bigger than everything: goes at the end

7Code line by line

8Dry run

9Complexity & remember

• Time O(n), space O(1). On LeetCode it shows as very fast, because n is only 10⁴.
• The teacher's "what if" question: if n could be 10⁹, would this pass? No. 10⁹ (or even 9 × 10⁸) steps is past the ~10⁸ limit, so it would TLE. The array is sorted, so the fix is binary search, O(n) → O(log n).

Part B · Binary search, return left

1The question

Same question. Now in O(log n), using the sorted order.

2What the constraints tell us

Same as Part A. Binary search is what makes this survive if n were 10⁹. Small values mean no overflow worries even in Java.

3Intuition

Why always the middle? Because comparing with the middle lets us drop half of the array with one decision. If the middle value is bigger than the target, the target belongs somewhere on the left, so the right half can go. If it's smaller, the left half can go.

We keep doing this until the range is empty. The new idea: when the range becomes empty, left is sitting exactly at the insert position.

4Building the conditions from examples

The teacher's board shows a 7-item sorted array (indexes 0 to 6) and target 3, which isn't in it. We'll use 1 2 4 5 6 8 9, which starts 1, 2, 4 like her linear-search walk.

• Equal → return mid. Checked first. If the middle value is the target, that index is the answer, the same as in basic binary search.
• Middle bigger than target (5 > 3) → the target belongs on the left. mid itself isn't the target, so right = mid - 1.
• Middle smaller than target → the target belongs on the right → left = mid + 1.

Following her board: after the first step the range is indexes 0–2. The middle there (value 2) is smaller than 3, so we move right. Now left, right and mid all land on the same index (2, value 4). She points out that when the range shrinks to a single index like this, that's where 3 belongs. 4 > 3 moves right to 1, the pointers cross, and left = 2 is the answer.

Loop condition: keep going while left <= right ("until left crosses right, and also when they're equal"), the same as basic binary search.

Why return left and not right?

The teacher's advice is to dry run it with pen and paper on different test cases and see for yourself. Her short reason: when they cross, right has stepped back to a place left was at earlier, a place already found to be too small, and that's why left moved past it. So left is the correct spot.

5Approach steps

1. left = 0, right = n - 1.
2. While left <= right: mid = left + (right - left) // 2.
3. nums[mid] == target → return mid.
4. nums[mid] > target → right = mid - 1.
5. Else → left = mid + 1.
6. After the loop → return left.

6Code (Python)

class Solution:
    def searchInsert(self, nums, target):
        left = 0
        right = len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid              # already present
            elif nums[mid] > target:
                right = mid - 1         # it belongs on the left
            else:
                left = mid + 1          # it belongs on the right
        return left                     # where the target would be inserted

class SolutionSaveAnswer:               # keep the best answer seen so far
    def searchInsert(self, nums, target):
        left, right = 0, len(nums) - 1
        ans = len(nums)                 # default: insert at the end
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] >= target:
                ans = mid               # mid works; maybe something earlier does too
                right = mid - 1
            else:
                left = mid + 1
        return ans

class SolutionRightIsMid:               # move right to mid, not mid - 1
    def searchInsert(self, nums, target):
        left, right = 0, len(nums)      # right = n: "at the end" is possible
        while left < right:             # stop when one candidate is left
            mid = left + (right - left) // 2
            if nums[mid] >= target:
                right = mid             # mid could be the answer, keep it
            else:
                left = mid + 1
        return left

7Code line by line

8Dry run

Her board example: target 3 in 1 2 4 5 6 8 9

Edge cases on 1 3 5 6

9Complexity & remember

• Time O(log n): half the range is dropped every step (n → n/2 → n/4 → … → 1, about log₂ n steps; for n = 10⁴ that's about 14). Space O(1).
• On LeetCode both versions show as "beats 100%". The teacher explains that's only because n ≤ 10⁴. With 10⁹ items the linear one would TLE and only binary search would pass.

The teacher's closing advice: watching isn't learning. Dry run it yourself on paper with a few targets (found, between, before all, after all), then write and submit the code yourself. Otherwise the "why left" logic won't stick.

Part C · Revision page

for S in (SolutionLinear, Solution, SolutionSaveAnswer, SolutionRightIsMid):
    s = S()
    print(s.searchInsert([1, 3, 5, 6], 5), s.searchInsert([1, 3, 5, 6], 2),
          s.searchInsert([1, 3, 5, 6], 7), s.searchInsert([1, 3, 5, 6], 0),
          s.searchInsert([1, 2, 4, 5, 6, 8, 9], 3))
# 2 1 4 0 2  (printed 4 times)

Based on this video: Search Insert Position | Classic Binary Search pattern