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 to Solve:

The problem can be efficiently solved using binary search. Here's a breakdown of the steps:

1. Initialization: Set left pointer to 0 and right pointer to nums.length - 1.

2. Binary Search Iteration: While left is less than or equal to right:

   • Calculate the mid index: mid = (left + right) / 2. Avoid (left + right) >> 1 to prevent potential overflow.
   • Compare nums[mid] with target:
     • If nums[mid] == target, the target is found, return mid.
     • If nums[mid] < target, the target is in the right half, so update left = mid + 1.
     • If nums[mid] > target, the target is in the left half, so update right = mid - 1.

3. Target Not Found: If the loop completes without finding the target, it means the target should be inserted. The left pointer will now point to the correct insertion index. Return left.

Explanation:

Binary search efficiently searches a sorted array by repeatedly dividing the search interval in half. If the target is not found, the final position of the left pointer indicates where the target would be inserted to maintain the sorted order. This approach guarantees O(log n) time complexity.

Code (Java):

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; // Target not found, left pointer indicates insertion index
    }
}

Complexity:

• Time Complexity: O(log n) - Due to the binary search algorithm.
• Space Complexity: O(1) - Constant extra space is used. The algorithm operates in-place.