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

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

1. Initialization: Set left pointer to 0 and right pointer to nums.size() - 1.
2. Iteration: While left is less than or equal to right:
   • Calculate the mid point: mid = left + (right - left) / 2. This prevents potential integer overflow.
   • Comparison:
     • If nums[mid] equals target, return mid (target found).
     • If nums[mid] is less than target, it means the target is in the right half. Update left = mid + 1.
     • If nums[mid] is greater than target, it means the target is in the left half. Update right = mid - 1.
3. Target Not Found: If the loop completes without finding the target, it means the target should be inserted at index left. Return left.

Explanation

Binary search is ideal for sorted arrays because it efficiently eliminates half of the search space with each comparison. The algorithm continuously narrows down the search range until either the target is found or the search space is exhausted. When the target is not found, the left pointer will point to the index where the target should be inserted to maintain the sorted order.

Code (C++)

#include <vector>

class Solution {
public:
    int searchInsert(std::vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;

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

            if (nums[mid] == target) {
                return mid; // Target found
            } else if (nums[mid] < target) {
                left = mid + 1; // Target is in the right half
            } else {
                right = mid - 1; // Target is in the left half
            }
        }

        return left; // Target not found, insertion point is at 'left'
    }
};

Complexity Analysis

• 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.