Problem Statement
Given a sorted array of nums consisting of distinct integers 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.
Example
Example 1:
Input: nums = [1, 3, 5, 6, 7], target = 5
Output = 2
Explanation: The target value 5 is found at index 2 in the nums array. Hence, the function returns 2.Example 2:
Input: nums = [1, 3, 5, 6, 7], target = 2
Output: 1
Explanation: The target value 2 is not found in the nums array. However, it should be inserted at index 1 to maintain the sorted order of the array.Example 3:
Input: nums = [1, 3, 5, 6, 7, 8], target = 9
Output: 7
Explanation: The target value 9 is not found in the nums array. However, it would be present at index equal to the size of array if inserted.Different Approaches
1️⃣ Linear Search (Brute Force)
Intuition:
Let's start with the simplest way to solve this problem. Imagine you're reading a book, and you want to find a specific page. You start from the beginning and turn each page one by one until you find the page you're looking for. If you don't find it, you know exactly where it should be inserted based on the pages you've turned so far.
Approach:
- Begin with the first number in the list. If the number matches the target, return the current index.
- If the number is greater than the target, return the current index as the position where the target should be inserted.
- If you reach the end of the list without finding the target, return the length of the list, as the target should be inserted at the end.
Code:
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
/* Public method to find the index of the
target or where it would be inserted*/
int searchInsert(vector<int> &nums, int target)
{
// Iterate through the vector
for (int i = 0; i < nums.size(); ++i) {
/* If current element is greater than
or equal to the target */
if (nums[i] >= target) {
// Return the current index
return i;
}
}
/* If target is greater than all elements,
return the size of the vector */
return nums.size();
}
};
int main()
{
vector<int> nums = {1, 3, 5, 6};
int target = 5;
// Create an instance of the Solution class
Solution sol;
// Find the insertion index
int ind = sol.searchInsert(nums, target);
cout << "The index is: " << ind << "\n";
return 0;
}
Complexity Analysis:
- Time Complexity:
O(N), whereNis the size of the given array. We are using the Linear Search algorithm, which iterates linearly resulting inNtime complexity. - Space Complexity:
O(1), as we are not using any extra space to solve this problem.
2️⃣ Binary Search (Optimal) Approach
Intuition:
Considering our example used in brute force approach, imagine you have a faster way to find the target, using a table of contents in a book where you can quickly skip to different sections instead of turning each page one by one. This is essentially what binary search accomplishes. It allows us to efficiently narrow down the search range by repeatedly dividing it in half.
In this specific problem, if the target itself is found, return its index. Otherwise, return the smallest index where the element is greater than the target. Upon observation, it becomes clear that the lower bound of the target serves this purpose. Therefore, for this problem, simply find the lower bound of the target. If no such element is found, return the size of the array.
Approach:
- Use two pointers to traverse the array, low and high, and an ans variable with the size of the array to store the answer. The low pointer starts at the first index, and the high pointer starts at the last index.
- Calculate the middle index, and compare arr[mid] with the given element. If arr[mid] is greater than or equal to the given element then we the update the ans variable with mid and search in the left half for a smaller index that also satisfies the condition.
- If arr[mid] is less than the given element, then we search in the right half by eliminating the left half. We do so by making the low pointer as mid+1.
- Continue the process until the low pointer crosses the high pointer. At this point, the ans variable will hold the answer.
Dry Run:
Initialization:
+-----+-----+-----+-----+
nums = | 1 | 3 | 5 | 6 |
+-----+-----+-----+-----+
0 1 2 3
target = 2First Iteration:
low = 0
high = 3
mid = low + (high - low)/2
= 0 + 3/2
= 1
+-----+-----+-----+-----+
nums = | 1 | 3 | 5 | 6 |
+-----+-----+-----+-----+
0 1 2 3
^ ^ ^
| | |
low mid high
target = 2
ans = 4 (length of the array)
Since nums[mid] is 3 which is greater than target = 2.
So update ans = mid = 1
and search the half left half by setting high = mid - 1
high = 1 - 1
high = 0Second Iteration:
low = 0
high = 0
mid = low + (high - low)/2
= 0 + 0/2
= 0
+-----+
nums = | 1 |
+-----+
0
^
|
low
target = 2
ans = 1
Since nums[mid] is 1 which is less than target = 2.
So move to the right half by setting low = mid + 1
= 1.
No change in ans.Loop Termination:
low = 1
high = 0
Since low > high, the loop terminates.
target = 2
ans = 1Code:
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
int searchInsert(vector<int> &nums, int target)
{
int n = nums.size();
int low = 0, high = n - 1;
int ans = n;
// Applying Binary Search Algorithm
while (low <= high) {
int mid = (low + high) / 2;
/* If mid element is greater than
or equal to target, update ans
and search the left half */
if (nums[mid] >= target) {
ans = mid;
high = mid - 1;
}
// Otherwise, search the right half
else {
low = mid + 1;
}
}
return ans;
}
};
int main()
{
vector<int> nums = {1, 3, 5, 6};
int target = 5;
// Create an instance of the Solution class
Solution sol;
// Find the insertion index
int ind = sol.searchInsert(nums, target);
cout << "The index is: " << ind << "\n";
return 0;
}OR
#include <iostream>
#include <vector>
using namespace std;
int searchInsert(vector<int>& nums, int target) {
int low = 0;
int high = nums.size() - 1;
// Perform binary search
while (low <= high) {
int mid = low + (high - low) / 2; // Calculate mid to avoid overflow
if (nums[mid] == target) {
return mid; // Found the target, return the index
}
else if (nums[mid] < target) {
low = mid + 1; // Search in the right half
}
else {
high = mid - 1; // Search in the left half
}
}
// If target is not found, return the insertion point
return low;
}
int main() {
vector<int> nums = {1, 3, 5, 6};
int target = 5;
cout << "Index: " << searchInsert(nums, target) << endl; // Output: 2
return 0;
}OR
class Solution {
public:
// Function to find the index where 'target' should be inserted in a sorted array 'nums'
int searchInsert(vector<int> &nums, int target) {
int left = 0; // Initialize left pointer to the start of the array
int right = nums.size() - 1; // Initialize right pointer to the end of the array
int pos = nums.size(); // Default position is set to the size of the array (end)
while(left <= right) {
int mid = left + (right - left) / 2; // Calculate mid-point to avoid overflow
if(nums[mid] == target) { // If mid element equals 'target'
pos = mid; // Update position to current mid index
right = mid - 1; // Move to the left half to find the first occurrence
} else if(nums[mid] > target) { // If mid element is greater than 'target'
pos = mid; // Update position to current mid index
right = mid - 1; // Move to the left half
} else { // If mid element is less than 'target'
left = mid + 1; // Move to the right half
}
}
return pos; // Return the position for insertion
}
};
Complexity Analysis:
- Time Complexity:
O(logN), whereNis the size of the given array. We are using the Binary Search algorithm, which divides the search space in half each time, resulting in a logarithmic time complexity. - Space Complexity:
O(1), as we are not using any extra space to solve this problem.