[LeetCode] 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.

Example:

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

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

Input: nums = [1,3,5,6], target = 7
Output: 4

Constraints:

• 1 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• nums contains distinct values sorted in ascending order.
• -10^4 <= target <= 10^4

Approach: The problem here is just to find the target itself or just greater element in the array so if you see this is a binary search problem with following changes:

1. If nums[mid] < target then obviously we need to go to the right side i.e. start = mid + 1
2. Else end = mid
3. Return end.

Implementation in C#:

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

    {

        int start = 0, end = nums.Length - 1 ;

        if (target < nums[start])

        {

            return start;

        }

        if (target > nums[end])

        {

            return end + 1;

        }

        while (start < end)

        {

            int mid = start + (end - start) / 2;

            if (nums[mid] < target)

            {

                start = mid + 1;

            }

            else

            {

                end = mid;

            }

        }    

        return end;

    }

Complexity: O(log(n))