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

1. Binary Search: Since the array is sorted, we can employ a binary search algorithm. This algorithm efficiently searches for a target value within a sorted array.

2. Initialization: Set left pointer to 0 and right pointer to len(nums) - 1.

3. Iteration: While left is less than or equal to right:

   • Calculate the mid index: mid = (left + right) // 2. Integer division is crucial here.
   • Comparison:
     • 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.

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

Explanation

The binary search repeatedly halves the search space. This ensures a logarithmic time complexity. When the target is not found, the left pointer converges to the correct insertion point. Consider Example 2:

• Initially, left = 0, right = 3.
• mid = 1, nums[mid] = 3. Since 3 > 2, right becomes 0.
• left = 0, right = 0. mid = 0, nums[mid] = 1. Since 1 < 2, left = 1.
• The loop terminates because left (1) > right (0). The function returns left, which is 1, the correct insertion point.

Code

def searchInsert(nums, target):
    """
    Finds the index of the target in a sorted array, or the insertion index if not found.

    Args:
        nums: A sorted list of integers.
        target: The integer to search for.

    Returns:
        The index of the target, or the insertion index.
    """
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return left

Complexity

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