Search insert position problem from LeetCode

Introduction to the problem

In this shot, we'll discuss binary search. The problem statement is given below:

We are given a sorted array of distinct integers nums and a target value. Our task is to find out the index if the target is found. If not, we need to return the index where the target would be inserted. Remember, if the target is not found, the index at which the target could be placed should still keep the array nums as sorted.

For example, let's assume that the given array is [1, 2, 4, 5, 6, 7], and the target value is 3. The solution for this input will be 2. Since the target could be inserted at index 2 to keep the array sorted.

Solution approach

Let's now discuss the approach to solve this problem. We can take some time to think about the solution to this problem and then proceed further.

We'll follow the steps mentioned below to solve the given problem:

  • We'll first apply the binary search algorithm on the given sorted array.
  • If the target value is found, we'll return that index.
  • If not, we'll process until our search space becomes empty. At this point, the index at which the element should be inserted is already saved while we dive our search space by half.

Example

#include <iostream>
#include <vector>
using namespace std;
int searchInsert(vector<int>& nums, int target) {
  int start = 0;
  int end = nums.size() - 1;
        
  while(start <= end){
    int mid = start + (end - start)/2;
    
    if (nums[mid] == target)
      return mid;
    else if (nums[mid] < target)
      start = mid + 1;
    else
      end = mid - 1;
  }
  
  return start;
}
int main() {
  vector<int> vec = {1, 2, 4, 5, 6, 7};
  int target = 3;
  int index = searchInsert(vec, target);
  cout << "Index: " << index;
  return 0;
}

Explanation

  • Lines 5–21: We create a function searchInsert(). This function will accept a vector of sorted integers and the target value. Next, it will apply the binary search algorithm
  • Lines 12 and 13: If the target is found, we return that index. If the target is not found, we continue executing the loop until our start index becomes greater than the end index. In the end, the value in the start variable will actually contain the index at which that element could be inserted, and the array will remain sorted after the insertion.
    • Lines 27 and 28: We call the function and print the index for the provided target.
      Note: To learn and solve more coding interview questions, refer to this course: Competitive Programming - Crack Your Coding Interview, C++.
      Free AI Mock Interviews
      Coding Interview
      Coding PatternsFree Interview
      Gain insights and practical experience with coding patterns through targeted MCQs and coding problems, designed to match and challenge your expertise level.
      System Design
      You TubeFree Interview
      Learn to design a video streaming platform like YouTube by tackling functional and non-functional requirements, core components, and high-level to detailed design challenges.

      Free Resources

      License: Creative Commons-Attribution-ShareAlike 4.0 (CC-BY-SA 4.0)