Given a sorted array arr[] and an integer X, return the index of X if it is present.
If X is not present, return the index where it should be inserted so that the array remains sorted.
Example 1
Input: arr = [1, 3, 5, 6], X = 5
Output: 2
Explanation: The value 5 is already present at index 2, so that index is returned.
Example 2
Input: arr = [1, 3, 5, 6], X = 2
Output: 1
Explanation: The value 2 is not present. If it is inserted at index 1, the array becomes [1, 2, 3, 5, 6], which is still sorted.
Brute Force Approach
The most direct idea is to move from left to right and stop at the first position where the current value becomes greater than or equal to X.
If that happens, the same index works in both cases. If the value is exactly X, that is its position. If the value is greater than X, that is the place where X should be inserted before it.
If the loop ends, that means every element is smaller than X, so the correct insert position is the end of the array.
Algorithm
Start from index
0and check each element one by one.If the current element is greater than or equal to
X, return that index because eitherXis found there or that is the correct insert position.If no such element is found after scanning the whole array, return the length of the array.
Key Points
If
Xis smaller than or equal to the first element, the answer is0.If every element is smaller than
X, returnn.
Dry Run
Search Insert Position Brute Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* Returns the index of x if it exists, otherwise returns the correct insert position. */ int searchInsertPosition(vector<int>& arr, int x) { // Check each position from left to right. for (int i = 0; i < (int)arr.size(); i++) { // The first value greater than or equal to x gives the answer. if (arr[i] >= x) { return i; } } return (int)arr.size(); }};// Driver code startsint main() { vector<int> arr = {1, 3, 5, 6}; int x = 2; Solution obj; cout << obj.searchInsertPosition(arr, x) << endl; return 0;}Complexity Analysis
Time Complexity: O(N), N is the length of array, because in the worst case the whole array may need to be scanned.
Space Complexity: O(1), because only a loop variable is used.
Optimal Approach
The useful observation is this: the answer is simply the first index where the array value becomes greater than or equal to X.
If X is present, that first valid index is exactly its position.
If X is missing, that same first valid index is the place where X should be inserted to keep the array sorted.
So this problem can be solved using the lower-bound pattern. In binary search language, whenever arr[mid] is greater than or equal to X, that index can be an answer, but there may still be an earlier valid index on the left side.
Algorithm
Start with two pointers,
lowat0andhighat the last index, because the answer can lie anywhere in the array.Keep a variable
answeras the length of the array. This is useful because if no valid index is found, the insert position automatically becomes the end of the array.Find the middle index using
mid = low + (high - low) / 2so the middle position is calculated safely.If
arr[mid] >= X, storemidinanswerbecause it is a valid position, then move left to check whether an earlier valid index exists.If
arr[mid] < X, move right because neithermidnor anything before it can be the answer.Continue until
lowbecomes greater thanhigh.Return
answer.
Dry Run
Search Insert Position Optimal Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* Returns the index of x if it exists, otherwise returns the correct insert position. */ int searchInsertPosition(vector<int>& arr, int x) { // Left boundary of the current search range. int low = 0; // Right boundary of the current search range. int high = (int)arr.size() - 1; // Starts as arr.size() so it remains correct when x belongs at the end. int answer = (int)arr.size(); // Keep searching while a valid range still exists. while (low <= high) { // Calculate the middle index safely. int mid = low + (high - low) / 2; // This position can hold x, so store it and try to find an earlier one. if (arr[mid] >= x) { answer = mid; high = mid - 1; } else { // Values up to mid are too small, so move to the right half. low = mid + 1; } } return answer; }};// Driver code startsint main() { vector<int> arr = {1, 3, 5, 6}; int x = 2; Solution obj; cout << obj.searchInsertPosition(arr, x) << endl; return 0;}Complexity Analysis
Time Complexity: O(log N), N is the length of array, because the search range becomes half in each step.
Space Complexity: O(1), because only a few variables are used.
FAQs
Q1. Is search insert position the same as lower bound?
Yes, for a sorted array this problem is the same as finding the first index where arr[index] >= X.
Q2. What should be returned if X is larger than all elements?
Return n, which means X should be inserted at the end of the array.
Q3. What should be returned if X is smaller than all elements?
Return 0, because the value should be inserted at the beginning.
Q4. Does this logic still work if X is already present?
Yes. The first index where the value is greater than or equal to X becomes the exact position of X.
Be the first to add a comment.