35搜索插入位置

35搜索插入位置 35搜索插入位置 题目描述

题目链接

C++代码

#pragma once
#include 
#include
using namespace std;


class Solution {
public:
	int searchInsert(vector& nums, int target)
	{
		cout << "目标值为：" << target << endl;
		int n = nums.size();
		for (int i = 0; i < n; i++)
		{
			//返回大于等于目标值的数字对应的下表
			if (nums[i] >= target)
			{
				return i;
			}	
		}
		//如果全部遍历没有符合条件的，则放在最后
		return n;
	}
};

//打印容器
void show_vector(vector& v)
{

	vector::iterator it;
	for (it = v.begin(); it != v.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}


int main()
{
	
	//创建容器
	vectorv;
	v.push_back(1);
	v.push_back(3);
	v.push_back(5);
	v.push_back(6);

	//打印容器
	cout << "测试容器：" << endl;
	show_vector(v);
	
	//测试

	Solution S;
	int res = S.searchInsert(v, 7);
	cout << "索引为：" << res << endl;

	system("pause");
	return 0;
}

运行结果

折半查找（二分查找） 根据题目的提示，可以采用二分查找的方法

核心代码如下

//使用二分法

class Solution {
public:
	int searchInsert(vector& nums, int target) 
	{
		//定义目标值在左闭右闭区间内
		int n = nums.size();
		int left = 0;
		int right = n - 1;

		while (left <= right)
		{
			int middle = (left + right) / 2;
			//中间值大于目标值
			if (nums[middle] > target)
			{
				right = middle - 1;
			}
			//中间值小于目标值
			else if (nums[middle] < target)
			{
				left = middle + 1;
			}
			//中间值等于目标值
			else
			{
				return middle;
			}
		}
		//如果循环结束都没发现说明要插入的位置应该在最前面或者最后面
		return right + 1;

	}
};