Arrays: Given an array that is sorted and a target, if the target is found, return the index. If not found, return the index where it would be if it were inserted

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