Search Insert Position

Given a sorted array and a target, return the index if the target is found. Otherwise, return the index where it would be inserted to keep the array sorted.

Function signature

func SearchInsert(nums []int, target int) int

Inputs / outputs

• nums: sorted array of integers.
• target: value to insert/search.
• Return: insertion index.

Example

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

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

Constraints

• 1 <= len(nums) <= 10_000

Core idea (near-solution)

Use lower-bound binary search to find the first index where nums[i] >= target.

Invariant: all elements before lo are < target; all elements at or after hi are >= target.

Algorithm (step-by-step)

1. Set lo = 0, hi = len(nums) (exclusive).
2. While lo < hi:
   • mid = lo + (hi-lo)/2.
   • If nums[mid] < target, set lo = mid + 1.
   • Else set hi = mid.
3. Return lo.

Correctness sketch

• Invariant: all elements before lo are < target; all elements at or after hi are >= target.
• The valid answer lies within the maintained [lo, hi] range.
• Each comparison discards half the range that cannot contain an answer.
• When the loop ends, the remaining boundary/index is correct.

Trace (hand walkthrough)

Example input:
nums = [1,3,5,6], target = 5
Output: 2

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

Walk:
- target=5: mid=1 (3) -> lo=2; mid=2 (5) -> found index 2
- target=2: mid=1 (3) -> hi=1; mid=0 (1) -> lo=1 -> insert at 1

Pitfalls to avoid

• Using an inclusive hi and returning the wrong boundary.
• Forgetting that the insertion index can be len(nums).

Complexity

• Time: O(log n).
• Extra space: O(1).

Implementation notes (Go)

• This is a standard lower-bound implementation.