Search Insert Position easy

Problem Statement

Given a sorted array of distinct integers nums and an 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 and Explanation

The problem requires finding the index of a target value in a sorted array. If the target is not present, we need to find the index where it should be inserted to maintain the sorted order. This suggests using a binary search algorithm, which has a time complexity of O(log n).

1. Binary Search Initialization: We start with left = 0 and right = nums.length - 1. These pointers define the search space within the array.

2. Iteration: While left <= right, we perform the following:

   • Calculate the middle index: mid = Math.floor((left + right) / 2).
   • Comparison:
     • If nums[mid] === target, the target is found at index mid, so we return mid.
     • If nums[mid] < target, the target must be in the right half of the array, so we update left = mid + 1.
     • If nums[mid] > target, the target must be in the left half of the array, so we update right = mid - 1.

3. Target Not Found: If the loop completes without finding the target, left will point to the index where the target should be inserted. This is because the binary search process effectively partitions the array until left and right cross each other, with left being the first index greater than or equal to the target.

Code (TypeScript)

function searchInsert(nums: number[], target: number): number {
    let left = 0;
    let right = nums.length - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (nums[mid] === target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return left; // Target not found, insert at index 'left'
};

Complexity Analysis

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