Search Insert Position

LeetCode Problem #35 (Easy)

Problem Statement

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Testcases

Example 1:

Input: [1,3,5,6], 5
Output: 2

Example 2:

Input: [1,3,5,6], 2
Output: 1

Example 3:

Input: [1,3,5,6], 7
Output: 4

Example 4:

Input: [1,3,5,6], 0
Output: 0

Prerequisite Knowledge

Binary Search

Refer to the Prerequisite Knowledge section in Random Pick with Weight:

Random Pick with Weight

Algorithm

Binary Search Approach

In this approach, we perform in-place sorting by taking two parameters of comparison into consideration.

1. Initialize two pointer variables to point to the extreme ends of the array.

2. Iterate until the condition (left <= right) breaks.

3. Calculate the mid value such that overflow is avoided.

4. If the target is found in the array, return the index value.

5. If the target is greater than the mid value, the searching proceeds in the right half of the array.

6. If the target is less than the mid value, the searching proceeds in the left half of the array.

7. If the code exits the loop

   a. This means that left >= right + 1.

   b. But, the target index is between [left, right + 1], so left <= right.

   c. From a and b, left = right + 1.

   So the index to be returned is at [left, left]->left or [right + 1, right + 1]->right + 1.

Time Complexity: O(logn)

Illustration

Consider the array [1, 3, 5, 6, 8], and target = 7.

• In the first pass, the search region spans the entire array.

mid_index = 0 + (4 - 1) / 2 = 2

[1,  3,  5,  6,  8]
 l       m       r

• In the second pass, since 7 > 5, we continue the search in the right half of the array by moving the left pointer up to the index, mid + 1.

mid_index = 3 + (4 - 3) / 2 = 3

[1,  3,  5,  6,  8]
             l   r
             m

• In the third pass, since 7 > 6, we continue the search in the right half of the array by moving the left pointer up to the index, mid + 1.

[1,  3,  5,  6,  8]
                 l   
                 r
                 m

• In the fourth pass, since 7 < 8, we continue the search by moving the right pointer down to the index, mid - 1.

[1,  3,  5,  6,  8]
             r   l   
                 m

Here, the value of the the left pointer becomes greater than the right pointer so the loop exits. The position of the left pointer or the position of the right pointer + 1 is the place where 7 must be inserted.

Insert 7 at index 4
[1, 3, 5, 6, 7, 8]

Code

int searchInsert(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    while(left <= right) {
        // Calculate mid value
        // Conventional (left + right) / 2 may cause overflow
        int mid = left + (right - left) / 2;
        
        // Return index value if the target is found in the array
        if(nums[mid] == target) {
            return mid;
        }
        // The target is in the right half of the array
        else if(nums[mid] < target) {
            left = mid + 1;
        }
        // The target is in the left half of the array
        else {
            right = mid - 1;
        }
    }
    // [1] When the code reaches this point, left >= right + 1
    // [2] Since the target index is between [left, right + 1], so left <= right + 1
    // [3] From [1] and [2], left = right + 1, so we can return left as the index value
    return left; 
}