4 搜索插入位置

4 搜索插入位置

作者: Turbo时间限制: 1S章节: 课程设计

问题描述 :

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: 

4

1 3 5 6

5

输出: 2

示例 2:

输入:

4

1 3 5 6

2

输出: 1

输入说明 :

输入三行：

第一行输入一个整数n表示数组nums的长度。

第二行输入n个整数表示数组nums的元素。

第三行输入一个整数表示需要查找的目标值target.

提示:

    1 <= n <= 10^4

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

    nums 为 无重复元素 的 升序 排列数组

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

输出说明 :

输出一个整数表示结果。

输入范例 :

4
1 3 5 6
7

输出范例 :

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;
}