easy Search Insert Position

Problem Statement

Given an array nums containing integers in non-decreasing order and integer target, return the index if the target is found. If not, return the index where it can be placed such that the final array elements are in non-decreasing order.

You must solve the problem in time.

Examples

• Example 1:

  • Input: nums = [2,4,6,8,10], target = 1
  • Expected Output: 0
  • Justification: The target number 1 does not exist in the array but should be inserted at index 0 to keep the array in ascending order.

• Example 2:

  • Input: nums = [1,3,7,9,11], target = 10
  • Expected Output: 4
  • Justification: The target number 10 is not present in the array. It fits between 9 and 11, making the fourth index (0-based indexing) its rightful position.

• Example 3:

  • Input: nums = [5,8,12], target = 12
  • Expected Output: 2
  • Justification: The number 12 is present at index 2 in the array.

Solution

To solve this problem, we will employ a binary search approach due to its runtime complexity, which fits the requirement for efficiency. The essence of binary search lies in dividing the search interval in half repeatedly, which significantly reduces the number of comparisons needed to find the target or determine its rightful position. This method works effectively because the input array is already sorted in ascending order, allowing us to make assumptions about where the target might be located.

Initially, we define two pointers representing the search interval's bounds: left at the start and right at the end of the array. In each iteration, we compare the target with the middle element of the search interval. If the target is less than the middle element, we move the right pointer to the middle, narrowing our search to the lower half. If the target is greater, we adjust the left pointer to just past the middle element, shifting our focus to the upper half. This process continues until left meets right, indicating the target's position or insertion point, thereby ensuring that our approach is both efficient and effective.

Step-by-Step Algorithm

1. Initialize Pointers: Start by initializing two pointers, left and right, to point at the start and end of the array, respectively. left is set to 0, and right is set to the length of the array minus one.

2. Binary Search Loop: While the left pointer is less than or equal to the right pointer, perform the following steps to narrow down the search for the target or its insertion position:

   • Calculate the middle index, mid, as the average of left and right ((left + right) / 2). To avoid potential overflow, you can use left + (right - left) / 2.
   • Compare the target value with the element at the middle index (nums[mid]).
     • If nums[mid] is equal to the target, then the target is found. Return the mid index as the position where the target exists within the array.
     • If nums[mid] is less than the target, it means the target, if it exists, must be in the right half of the current segment. Update left to mid + 1 to narrow the search to the right half.
     • If nums[mid] is greater than the target, this indicates that the target, if present, is in the left half. Update right to mid - 1 to focus the search on the left half.

3. Identify Insert Position: If the loop terminates without finding the target (i.e., left > right), it means the target does not exist in the array and should be inserted. At this point, left points to the index where the target should be inserted to maintain the sorted order of the array. Return left as the insertion index.

Algorithm Walkthrough

Let's consider the input: nums = [2,4,6,8,10], target = 1.

• Step 1: Initialize left = 0 and right = 4 (since the array has 5 elements, and indices start at 0).

• Step 2: Enter the binary search loop:

  • First Iteration:
    • Calculate mid = (0 + 4) / 2 = 2. nums[2] is 6.
    • Since 6 is greater than 1, update right to mid - 1 = 1.
  • Second Iteration:
    • left is still 0, and right is now 1. Calculate mid = (0 + 1) / 2 = 0 (integer division).
    • nums[0] is 2, which is greater than 1. So, update right to mid - 1 = -1.
  • Third Iteration:
    • Now, both left >right. So, the loop terminates.

• Step 3: Since the loop has terminated and we did not find the target value of 5, left is at the position where 5 should be inserted to maintain the array's order. In this case, left is 0, indicating that the target number 5 should be inserted at index 2.

Code

public class Solution {

  // Method to find the insert position or the index of the target
  public int searchInsert(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
      int mid = left + (right - left) / 2; // Find the middle element
      if (nums[mid] == target) return mid; // Target found
      else if (nums[mid] < target) left = mid + 1; // Search in the right half
      else right = mid - 1; // Search in the left half
    }
    return left; // The correct insert position
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    // Example 1
    System.out.println(solution.searchInsert(new int[] { 2, 4, 6, 8, 10 }, 1));
    // Example 2
    System.out.println(solution.searchInsert(new int[] { 1, 3, 7, 9, 11 }, 10));
    // Example 3
    System.out.println(solution.searchInsert(new int[] { 5, 8, 12 }, 12));
  }
}

Complexity Analysis

Time Complexity:

• The algorithm uses binary search to find the target's position or the insertion point in the array. Since binary search divides the search interval in half at each step, the time complexity is logarithmic.
• With each comparison, it either finds the target or halves the search range, leading to a maximum of comparisons, where n is the number of elements in the array.

Space Complexity:

The algorithm uses a fixed amount of extra space for variables, regardless of the input size. Therefore, the space complexity is constant, as it does not require additional space that scales with the input size.