Solution Explanation: Search Insert Position

The problem asks to find the index where a target value should be inserted into a sorted array nums to maintain its sorted order. If the target already exists, return its index.

Two main approaches are presented:

Approach 1: Iterative Binary Search

This approach leverages the efficiency of binary search because the input array is sorted. The core idea is to repeatedly halve the search space until the target is found or the search space is exhausted.

• Algorithm:

  1. Initialize two pointers, l (left) and r (right), to the start and end of the array (inclusive and exclusive, respectively).
  2. While l < r:
     • Calculate the middle index mid = (l + r) // 2 (integer division).
     • If nums[mid] >= target, the target (if present) is in the left half, so update r = mid.
     • Otherwise, the target is in the right half, so update l = mid + 1.
  3. Return l. This is because after the loop finishes, l points to the index where the target should be inserted. If target was found, l will be its index.

• Time Complexity: O(log n), where n is the length of the array. This is the characteristic time complexity of binary search.

• Space Complexity: O(1), as we use only a constant amount of extra space.

Approach 2: Using Built-in Binary Search Functions

Many programming languages provide built-in functions for binary search. These functions often return either the index of the found element or a negative value indicating the insertion point.

• Algorithm:

  1. (Python) Use bisect_left(nums, target) from the bisect module. This function returns the index where target should be inserted to maintain order.
  2. (Java) Use Arrays.binarySearch(nums, target). This function returns the index if target is found; otherwise, it returns -insertion_point - 1.
  3. (C++) Use lower_bound(nums.begin(), nums.end(), target) - nums.begin(). This finds the iterator to the first element not less than target, and subtracts the beginning iterator to get the index.
  4. (Go) Use sort.SearchInts(nums, target). This function returns the index where the target should be inserted.

• Time Complexity: O(log n), as it is based on the underlying binary search algorithm of the built-in function.

• Space Complexity: O(1), as it usually uses a constant amount of extra space.

Code Examples (Approach 1 - Iterative Binary Search):

The code examples below demonstrate the iterative binary search approach in multiple languages. The core logic remains the same, differing only in syntax and function names.

• Python:

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums)
        while l < r:
            mid = (l + r) // 2
            if nums[mid] >= target:
                r = mid
            else:
                l = mid + 1
        return l

• Java:

class Solution {
    public int searchInsert(int[] nums, int target) {
        int l = 0, r = nums.length;
        while (l < r) {
            int mid = (l + r) >>> 1; // Use >>> for unsigned right shift
            if (nums[mid] >= target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}

• C++:

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int l = 0, r = nums.size();
        while (l < r) {
            int mid = (l + r) >> 1;
            if (nums[mid] >= target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
};

(Other languages like Go, JavaScript, TypeScript, Rust, and PHP would have similar implementations with minor syntactic variations.)

Code Examples (Approach 2 - Built-in Functions):

This approach is even more concise, leveraging the language's built-in binary search capabilities.

• Python:

import bisect
 
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        return bisect.bisect_left(nums, target)

• Java:

import java.util.Arrays;
 
class Solution {
    public int searchInsert(int[] nums, int target) {
        int i = Arrays.binarySearch(nums, target);
        return i < 0 ? -i - 1 : i;
    }
}

(Similar concise solutions exist for C++, Go, and other languages with built-in binary search functions.)

Both approaches offer optimal O(log n) time complexity, making them efficient for large input arrays. The choice between them depends on preference and whether you want to utilize built-in functions for brevity.