leecode 解题总结：35. Search Insert Position

#include <iostream>#include <stdio.h>#include <vector>using namespace std;/*问题:Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.You may assume no duplicates in the array.Here are few examples.[1,3,5,6], 5 → 2[1,3,5,6], 2 → 1[1,3,5,6], 7 → 4[1,3,5,6], 0 → 0分析:这是二分查找的lowwer_bound的问题。输入:4 51 3 5 64 21 3 5 64 71 3 5 64 01 3 5 6输出2140关键:1 lowwer_bound:		//low == high时，如果找到，就返回		if(nums.at(low) >= target)		{			return low;		}		//说明是数组最后一个元素，返回low+1		else		{			return low + 1;		}*/class Solution {public:	int lower_bound(vector<int>& nums , int target)	{		if(nums.empty())		{			return -1;		}		int low = 0;		int high = nums.size() - 1;		int mid;		while(low < high)		{			mid  = low + (high - low) / 2;			//中间大于目标值，目标值，mid可能是结果,继续在左半部分寻找			if(nums.at(mid) >= target)			{				high = mid;			}			//中间值 < 目标值，mid不可能是结果，在右半部分寻找			else			{				low = mid + 1;			}		}		//low == high时，如果找到，就返回		if(nums.at(low) >= target)		{			return low;		}		//说明是数组最后一个元素，返回low+1		else		{			return low + 1;		}	}    int searchInsert(vector<int>& nums, int target) {		int high = lower_bound(nums , target);		return high;    }};void PRocess(){	int num ;	int value;	vector<int> nums;	int target;	Solution solution;	vector<int> results;	while(cin >> num >> target)	{		nums.clear();		for(int i  = 0 ; i < num ; i++)		{			cin >> value;			nums.push_back(value);		}		int result = solution.searchInsert(nums , target);		cout << result << endl;	}}int main(int argc , char* argv[]){	process();	getchar();	return 0;}