Search Insert Position easy

Problem Statement

Given a sorted array of distinct integers nums and a target integer target, 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.

Example 1

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

Example 2

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

Steps

The problem requires finding the index of the target element or the index where it should be inserted to maintain sorted order. A binary search algorithm is the most efficient approach to achieve O(log n) runtime.

1. Initialize: Set left to 0 and right to nums.Length - 1.
2. Binary Search: While left is less than or equal to right:
   • Calculate the middle index mid as (left + right) / 2.
   • If nums[mid] equals the target, return mid.
   • If nums[mid] is less than the target, update left to mid + 1 (search in the right half).
   • Otherwise (nums[mid] is greater than the target), update right to mid - 1 (search in the left half).
3. Insertion Point: If the loop completes without finding the target, left will point to the index where the target should be inserted to maintain the sorted order. Return left.

Explanation

The binary search repeatedly divides the search interval in half. If the target is found, its index is returned immediately. If the target is not found, the algorithm converges to the point where the target would be inserted to maintain the sorted order. This is because the left pointer is always updated to point to the smallest index greater than or equal to the target, and this remains true even after the loop terminates.

Code

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

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

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

        return left; // Insertion point if target not found
    }
}

Complexity

• Time Complexity: O(log n) due to the binary search algorithm.
• Space Complexity: O(1). The algorithm uses a constant amount of extra space regardless of the input size.