35. Search Insert Position

EasyArrayBinary Search
Leetcode Link

Problem Description

The problem asks us to find the position in a sorted array where a target value either is found or would be inserted to maintain the array's order. You are given a sorted array with distinct integers and a target value. The task is to check if the target is present in the array. If the target is found, you need to return its index. If the target is not found, you need to return the index where it would be inserted to keep the array sorted. The key requirement is that the solution must operate with a runtime complexity of O(log n), suggesting that we must use an efficient algorithm like binary search that repeatedly divides the search interval in half.

Intuition

To achieve the O(log n) runtime complexity, we utilize the binary search algorithm. The intuition behind this approach is based on the sorted nature of the array. At each step, binary search compares the target value to the middle element of the array. If the target is equal to the middle element, we have found the target, and its index is returned. If the target is less than the middle element, it must be in the left sub-array, and we continue the search there; if it's more, we continue in the right sub-array.

Our search domain decreases by half with each comparison, which is why binary search is so efficient.

For the case where the element is not found, the position where it would be inserted is the point where our search space narrows down to an empty range, and left will have moved to the index where the target value can be inserted to maintain the sorted array property. This is because, throughout the search, left is maintained as the boundary where all elements to its left are less than the target, making it the correct insertion position for the target value.

Learn more about Binary Search patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which data structure is used to implement recursion?

Solution Approach

The solution implements a binary search algorithm to find the target's index or the insertion point in the array to maintain a O(log n) runtime complexity. The main steps of the algorithm used in the solution are as follows:

  1. We initialize two pointers, left and right, representing the search space's boundaries within the array. left is set to 0, and right is set to the length of the array.
  2. We enter a loop that continues until left < right, which means there is still a range to be searched. Inside this loop, a middle index mid is calculated, which is the average of left and right indexes, for the current search interval. Here, we use a binary shift operation >> 1 which is equivalent to dividing by 2.
  3. We compare the middle element nums[mid] with the target. If the middle element is greater than or equal to the target (nums[mid] >= target), we know the target, if it exists, is to the left of mid or at mid. So, we move the right pointer to mid, narrowing the search space to the left half.
  4. If the middle element is less than the target (nums[mid] < target), the target, if it exists, is to the right of mid. Therefore, we move the left pointer to mid + 1, narrowing the search space to the right half.
  5. When the loop exits, the left pointer indicates the position where the target is found or should be inserted. The condition of the loop ensures that left and right pointers converge on the insertion point if the target is not found.

This iterative halving of the search space is what allows the binary search algorithm to run in O(log n) time.

By using binary search, we efficiently locate the target value or determine the correct insertion point with minimal comparisons, making the algorithm very effective for large sorted datasets.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Example Walkthrough

Let's consider the sorted array nums = [1, 3, 5, 6] and the target value target = 5. We want to find the index of the target value or the index where it should be inserted to maintain the sorted order.

  1. Initialize two pointers, left = 0 and right = length_of_array which is 4.
  2. Loop while left < right:
    • Calculate mid as (left + right) >> 1 which is (0 + 4) >> 1, giving us mid = 2.
    • Check if nums[mid] is greater than, less than, or equal to the target:
      • nums[2] is 5, which is equal to the target of 5.
      • Since the middle element is equal to the target, we have found the target at index 2.
  3. The loop ends as we found the target.
  4. Return the mid index, which is 2.

The 5 is located at index 2 in the array, so the function returns 2 as the index where 5 is found.

Now let's consider a different target value target = 2.

  1. Initialize two pointers, left = 0 and right = 4.
  2. Continue the loop while left < right:
    • Calculate mid as (left + right) >> 1 which is (0 + 4) >> 1, giving us mid = 2.
    • Check if nums[mid] is greater than, less than, or equal to target:
      • nums[2] is 5, which is greater than the target of 2.
      • Since nums[mid] is greater than the target, update right to mid to continue searching in the left sub-array.
  3. Now left = 0 and right = 2; calculate new mid as (0 + 2) >> 1, which is 1.
  4. Check nums[mid] against target:
    • nums[1] is 3, which is greater than the target.
    • Update right to mid to continue searching in the left sub-array.
  5. Now left = 0 and right = 1; loop exits as left is now equal to right.
  6. Since the target 2 wasn't found, we return left which is the position where 2 would be inserted to maintain the sorted order.

The target 2 would be inserted at index 1 to maintain the sorted order, so the function returns 1.

Solution Implementation

1from typing import List  # Import the List type from typing module for type hints.
2
3class Solution:
4    def search_insert(self, nums: List[int], target: int) -> int:
5        # Initialize two pointers for the search boundaries.
6        left, right = 0, len(nums)
7      
8        # Use binary search to find the insert position.
9        while left < right:
10            # Calculate the middle index to compare with the target.
11            mid = (left + right) // 2  # Using // for integer division in Python 3.
12            # If the middle element is greater than or equal to the target,
13            # search the left half including the current middle.
14            if nums[mid] >= target:
15                right = mid
16            # If the middle element is less than the target,
17            # search the right half excluding the current middle.
18            else:
19                left = mid + 1
20      
21        # The left pointer will end up at the insert position, so return it.
22        return left
23
24# Example usage:
25# sol = Solution()
26# print(sol.search_insert([1, 3, 5, 6], 5))  # Output: 2
27# print(sol.search_insert([1, 3, 5, 6], 2))  # Output: 1
28# print(sol.search_insert([1, 3, 5, 6], 7))  # Output: 4
29# print(sol.search_insert([1, 3, 5, 6], 0))  # Output: 0
30
1class Solution {
2    public int searchInsert(int[] nums, int target) {
3        // Initialize the left and right pointers. 
4        // Right is initially set to the length of the array rather than the last index.
5        int left = 0, right = nums.length;
6      
7        // Binary search to find the target or the insertion point.
8        while (left < right) {
9            // Calculate the middle index. 
10            // Use unsigned right shift to avoid potential overflow for large left/right.
11            int mid = (left + right) >>> 1;
12          
13            // If the current element at the middle index is greater than or equal to the target,
14            // narrow the search to the left half (inclusive of mid).
15            if (nums[mid] >= target) {
16                right = mid;
17            } else {
18                // Otherwise, narrow the search to the right half (exclusive of mid).
19                left = mid + 1;
20            }
21        }
22        // Since the algorithm is looking for the insertion point, left will be the correct index
23        // whether the target is found or not.
24        return left;
25    }
26}
27
1#include <vector> // Include necessary header for using vectors.
2
3// Solution class as provided in the original problem statement.
4class Solution {
5public:
6    // searchInsert function to determine the index at which the target should be inserted or is found in a sorted array.
7    int searchInsert(std::vector<int>& nums, int target) {
8        // Initialize the search bounds.
9        int left = 0; // 'left' is the start of the search range.
10        int right = nums.size(); // 'right' is set to one past the end of the search range.
11
12        // Binary search loop.
13        while (left < right) { // While the search range is not empty, continue searching.
14            int mid = (left + right) / 2; // Calculate the midpoint to prevent potential overflow.
15          
16            // Compare the middle element to the target.
17            if (nums[mid] >= target)
18                // If the middle element is greater than or equal to the target,
19                // narrow the search to the left half, excluding the current mid.
20                right = mid;
21            else
22                // Otherwise, narrow the search to the right half, excluding the current mid.
23                left = mid + 1;
24        }
25
26        // 'left' will be the position where the target should be inserted or where it is found.
27        return left; 
28    }
29};
30
1// Define the function searchInsert with input parameters 'numbers', an array of numbers,
2// and 'target', the number to search for, which returns the index of the target number or the insert position.
3function searchInsert(numbers: number[], target: number): number {
4
5    // Define 'start' and 'end' variables representing the search range within the array.
6    let start: number = 0;
7    let end: number = numbers.length;
8
9    // Continue searching while 'start' is less than 'end'.
10    while (start < end) {
11
12        // Calculate the middle index of the current search range.
13        const mid: number = Math.floor((start + end) / 2);
14
15        // If the element at 'mid' is greater than or equal to the 'target',
16        // narrow the search range to the left half by setting 'end' to 'mid'.
17        if (numbers[mid] >= target) {
18            end = mid;
19        } 
20      
21        // Otherwise, narrow the search range to the right half by setting 'start' to 'mid + 1'.
22        else {
23            start = mid + 1;
24        }
25    }
26
27    // Return the 'start' index, which is the insert position of the 'target'.
28    return start;
29}
30
Not Sure What to Study? Take the 2-min Quiz：

Which two pointer technique does Quick Sort use?

Time and Space Complexity

Time Complexity

The provided code implements a binary search algorithm. In every iteration, it halves the segment of the nums list it is considering by adjusting either the left or right pointers. The time complexity of binary search is O(log n), where n is the number of elements in the nums list, due to the list's reduction by half in each iteration of the while loop.

Space Complexity

The space complexity of the code is O(1). This is because it uses a constant amount of space for the variables left, right, and mid regardless of the input size. No additional memory is allocated that is dependent on the size of the input list.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What are the most two important steps in writing a depth first search function? (Select 2)

Recommended Readings

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫