leecode 解题总结：34. Search for a Range

#include <iostream>#include <stdio.h>#include <vector>using namespace std;/*问题:Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.Your algorithm's runtime complexity must be in the order of O(log n).If the target is not found in the array, return [-1, -1].For example,Given [5, 7, 7, 8, 8, 10] and target value 8,return [3, 4].分析:这是二分查找的lower_bound和upper_bound的问题输入:6(数组元素个数) 8(待查找元素)5 7 7 8 8 106 125 7 7 8 8 101 112 22 2输出3 4-1 -10 00 1关键:1vector<int> results(2 , -1);//vector(n,val)2 		//找不到		if(-1 == low)		{			vector<int> results(2 , -1);//vector(n,val)			return results;		}		//如果找到，但是只有一个元素		else		{			vector<int> results;			results.push_back(low);			results.push_back(high - 1);			return results;		}3 在upper_bound中，		//low == high时，如果找到，就返回		if(nums.at(low) > target)		{			return low;		}		//如果发现找不到，就返回low+1(最后一定low为数组长度)		else		{			return low + 1;		}*/class Solution {public:	//寻找到第一个>=target的位置index,使得即使该元素找不到，插入该元素也有序	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;		}		else		{			return -1;		}	}	//找到第一个>target的元素的下标	int upper_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(最后一定low为数组长度)		else		{			return low + 1;		}	}    vector<int> searchRange(vector<int>& nums, int target) {		int low = lower_bound(nums , target);		int high = upper_bound(nums , target);		//找不到		if(-1 == low)		{			vector<int> results(2 , -1);//vector(n,val)			return results;		}		//如果找到，但是只有一个元素		else		{			vector<int> results;			//如果只有一个元素,那么high = low + 1			if(-1 == high)			{				high = low + 1;			}			results.push_back(low);			results.push_back(high - 1);			return results;		}    }};void PRint(vector<int>& results){	if(results.empty())	{		cout << "no result" << endl;		return;	}	int size = results.size();	for(int i = 0 ; i < size ; i++)	{		cout << results.at(i) << " ";	}	cout << endl;}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);		}		results = solution.searchRange(nums , target);		print(results);	}}int main(int argc , char* argv[]){	process();	getchar();	return 0;}