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 set right = mid - 1, discarding the middle and the upper half so our search narrows 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: The loop ended with left = 0 and target = 1 was not found, so 1 should be inserted at index 0 to keep the array sorted. Return left = 0.

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.

🎯 STRICT STANDOUT — Solution Search Insert Position

1. Why / judgment

This is textbook lower_bound, not “find or fail”. Sorted non-decreasing array ⇒ binary search returns the leftmost index where the target may sit without breaking order. Interview pressure point is the loop invariant: maintain the answer in [lo, hi] with hi = mid or lo = mid+1 so that when the loop ends, lo is the insert index. Linear scan is correct but violates the O(log n) contract; hash maps lose order and cannot answer insert position.

2. Big-O derivation (K11)

Binary search: each step halves [lo,hi]; iterations ≤ ⌈log2(n+1)⌉ + O(1).
Time Θ(log n). Space Θ(1) iterative (Θ(log n) if recursive stack).
Trace nums=[1,3,7,9,11], target=10:
  lo=0 hi=5 mid=2 nums[2]=7 < 10 → lo=3
  lo=3 hi=5 mid=4 nums[4]=11 ≥ 10 → hi=4
  lo=3 hi=4 mid=3 nums[3]=9 < 10 → lo=4
  lo=4 hi=4 → return 4 ✓
Trace target=1 on [2,4,6,8,10]: all mids ≥1 collapse to lo=0 ✓
Trace present target=12 on [5,8,12]: lands on index 2 ✓

3. Pattern + when-NOT (K12)

Name: BINARY SEARCH / LOWER_BOUND INSERT INDEX

Recognition: sorted array; “index of target or where it would be inserted to keep order”; must be O(log n).

When-NOT: Unsorted array → cannot BS; sort first (changes indices) or linear scan. Need all occurrences of target → lower_bound + upper_bound, not single insert index. Need true multiset with dynamic inserts → balanced BST / policy_based_data, not one-shot array BS.

4. Edge hand-run (K13)

empty [] target=5 → insert 0.
single [7] target=3 → 0; target=7 → 0; target=9 → 1.
all equal [2,2,2] target=2 → 0 (leftmost insert among equals for lower_bound).
target larger than all → return n.
2-element [1,3] target=2: lo/hi must converge without infinite loop → mid=0 or 1, ends lo=1.

5. Interviewer follow-ups (model answers)

Q1. Why return lo not mid after the loop?
A: Loop ends when lo==hi (or lo>hi depending on template); lo is the first feasible insert slot. mid is only a probe, not the answer.

Q2. What if the array has duplicates and target exists?
A: Classic lower_bound returns the first index of target (or insert before later equals). Spec usually accepts any correct insert among equal block if only “keep sorted”; still use consistent lower_bound.

Q3. Is mid = (lo+hi)//2 overflow-safe?
A: In languages with fixed-width ints use lo+(hi-lo)//2. Python int is unbounded so (lo+hi)//2 is fine.

6. Short drills

Drill A: [1,3,5,6] target=5 → 2; target=2 → 1; target=7 → 4; target=0 → 0.
Drill B: prove 2-element no infinite loop under while lo < hi template.
Drill C: implement upper_bound (first > target) and contrast with insert index.