Example 1: Input: [1,2,3,6], 6 Output: 3 Example 2: Input: [1,2,3,6], 5 Output: 3
Method 1: By using “lower_bound” STL function.
By using “lower_bound” you will get the index of the target if found, if not the index it returns is the correct position to insert that target value.
Method 2: By using binary search method.
By using binary search, we can achieve the same solution.
Solution in C++
#include<iostream> #include<string> #include<set> #include<vector> using namespace std; // by using STL methods int search_or_insert_method_1(vector<int> &array, int target) { return lower_bound(array.begin(), array.end(), target) - array.begin(); } // by using binary search 2 times. int search_or_insert_method_2(vector<int> &array, int target) { int start = 0; int end = array.size(); int mid; while (start < end) { mid = (start + end) / 2; if (array[mid] >= target) end = mid; else start = mid + 1; } return start; } int main() { vector<int> array = {1, 2, 3, 4, 4, 4, 4, 5, 6}; //test case 1 int target = 4; //test case 2 //int target = 7; cout<<"The given array is "<<endl; for (int i = 0; i < array.size(); i++) { cout <<array[i] << " "; } cout<<endl<<"The target is = "<<target<<endl; cout<<"The result using method 1 is "<<search_or_insert_method_1(array, target)<<endl; cout<<"The result using method 2 is "<<search_or_insert_method_2(array, target)<<endl; return 0; }
Output:
The given array is 1 2 3 4 4 4 4 5 6 The target is = 4 The result using method 1 is 3 The result using method 2 is 3
Fredchess
How will we test the second target(target = 7)?
prodevelopertutorial
There is only one target to be searched