Exercise 3: Search Insert Position

Your Task

Write a function search_insert(nums, target) that returns:

• The index of target if it exists in the sorted list, or
• The index where it should be inserted to keep the list sorted.

You can assume there are no duplicates.

---

Examples

print(search_insert([1, 3, 5, 6], 5))   # 2  (found at index 2)
print(search_insert([1, 3, 5, 6], 2))   # 1  (insert between 1 and 3)
print(search_insert([1, 3, 5, 6], 7))   # 4  (insert at end)
print(search_insert([1, 3, 5, 6], 0))   # 0  (insert at start)

---

Expected Complexity

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

---

Approach

This is binary search with a twist — instead of returning -1 on failure, return lo.

When the loop ends (lo > hi), lo is exactly the position where the target would go. Think about why:

• Every time the target is too big, you move lo up past mid
• Every time the target is too small, you move hi below mid
• When they cross, lo is sitting at the first value larger than target — the insertion point

---

Starter Code

def search_insert(nums, target):
    pass

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

---

Hints