C# LeetCode 35: Search Insert Position

Problem

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

First Approach - O(n)

Edge Cases:

• If target is less than the first element, return 0.
• If target is greater than the last element, return nums.Length.

Linear Scan:

• Iterate through the array.
• If an element equals the target → return its index.
• If the target lies between nums[i] and nums[i + 1] return i + 1.

First Attempt Code

public int SearchInsert(int[] nums, int target)
{
    if (target < nums[0])
    {
        return 0;
    }

    if (target > nums[nums.Length - 1])
    {
        return nums.Length;
    }

    for (int i = 0; i < nums.Length; i++)
    {
        if (nums[i] == target)
        {
            return i;
        }

        if (i < nums.Length - 1 && target > nums[i] && target < nums[i + 1])
        {
            return i + 1;
        }
    }

    return 0;
}

Although a good solution, it doesn't fulfil the O(log n) criteria.

Lets look at another solution

Better Approach - O(log n)

We can utilise a binary search algorithm, this reduces the numbers to scan by 50% with each iteration. Each iteration of binary search cuts the search space in half, so even with 1,000 elements, at most ~10 comparisons are needed.

Example:

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

left=0, right=3 → mid=1 → nums[1]=3 < 5 → move left
left=2, right=3 → mid=2 → nums[2]=5 == 5 → return 2

We need to eliminate the need for multiple edge checks, which can be achieved, as the loop naturally returns the index.

Handles all cases (found / not found / before first / after last) without extra loops.

Better Attempt

public int SearchInsert(int[] nums, int target)
{
    int left = 0, right = nums.Length - 1;

    while (left <= right)
    {
        int mid = left + (right - left) / 2;

        if (nums[mid] == target)
            return mid;
        else if (nums[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return left;
}