4 search insertion location

4  Search insert location

author : Turbo The time limit : 1S chapter :  curriculum design

Problem description :

Given a sort array and a target value , Find the target value in the array , And return its index . If the target value does not exist in the array , Return to where it will be inserted in sequence .

Please use a time complexity of O(log n) The algorithm of .

Example 1:

Input : 

4

1 3 5 6

5

Output : 2

Example 2:

Input :

4

1 3 5 6

2

Output : 1

Enter description :

Enter three lines ：

Enter an integer in the first line n Represents an array nums The length of .

Second line input n An integer represents an array nums The elements of .

In the third line, enter an integer to indicate the target value to be searched target.

Tips :

    1 <= n <= 10^4

    -10^4 <= nums[i] <= 10^4

    nums by No repeating elements Of Ascending Arrange arrays

    -10^4 <= target <= 10^4

The output shows that :

Output an integer to represent the result .

Input example :

4
1 3 5 6
7

Output example :

4

#include<iostream>
using namespace std;
void search(int arr[],int target,int length)
{
	int left = 0;
	int right = length - 1;
	if (arr[length - 1] < target)
	{
		cout << length;
		length++;
		return;
	}
	else if (arr[0] > target)
	{		
		cout << 0;
		length++; 
		return;
	}
	while (left <= right)
	{
		int mid = left + (right - left) / 2;
		if (arr[mid] == target)
		{
			cout<<mid;
			return;
		}
		else if (arr[mid] < target)
		{
			left = mid + 1;
		}
		else if (arr[mid] > target)
		{
			right = mid - 1;
		}
		cout<< left;
		return;
	}
	
}
int main()
{
	int arr[100000];
	int length = 0;
	cin >> length;
	for (int i = 0; i < length; i++)
	{
		cin >> arr[i];
	}
	int target = 0;
	cin >> target;

	search(arr, target, length);
	return 0;
}