34. 在排序数组中查找元素的第一个和最后一个位置

题目链接

#pragma once
#include 
#include

using namespace std;


//打印容器
void show_vector(vector& v)
{
	vector::iterator it;
	for (it = v.begin(); it != v.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}



class Solution {
public:
	vector searchRange(vector& nums, int target) 
	{
		//创建容器用于存放元素索引
		vectorres;
		//创建容器-不符合条件时的输出
		vectorno_res(2,-1);
		//打印不符合要求的输出
		cout << "不符合要求的输出：";
		show_vector(no_res);

		int n = nums.size();
		for (int i = 0; i < n; i++)
		{
			//关键字等于目标值时将索引添加到res容器
			if (nums[i] == target)
			{
				res.push_back(i);
				continue;
			}
		}

		//添加元素后，容器为空，输出不符合条件的容器
		//测试容器中没有目标值的情况
		if (res.empty())
		{
			return no_res;
		}
		//添加元素后若容器不为空
		else
		{
			//创建结果容器，存放上述容器的第一个元素和最后一个元素
			//1.测试容器中只有一个目标值
			//2.测试容器中有多个个目标值
			vectorresult_v;
			result_v.push_back(res.front());
			result_v.push_back(res.back());
			return result_v;
		}

	}
};





int main()
{
	
	vectorv;
	v.push_back(5);
	v.push_back(7);
	v.push_back(7);
	v.push_back(8);
	v.push_back(8);
	v.push_back(10);

	cout << "测试容器中的元素：";
	show_vector(v);


	Solution S;
	vector result = S.searchRange(v, 8);

	cout << "得到的结果：" ;
	show_vector(result);

	system("pause");
	return 0;
}

//使用二分法

class Solution {
public:
	//获取左边界
	int getLeftBorder(vector& nums, int target)
	{
		//左右边界初始值
		int left = 0;
		int right = nums.size() - 1;
		//边界结果
		int ans = nums.size();

		while (left <= right) 
		{
			int middle = (left + right) / 2;
			if (nums[middle] >= target)
			{
				right = middle - 1;
				ans = middle;
			}
			else {
				left = middle + 1;
			}
		}
		return ans;
	}

	//获取右边界
	int getRightBorder(vector& nums, int target) 
	{
		int left = 0;
		int right = nums.size() - 1;
		//边界结果
		int ans = nums.size();

		while (left <= right) {
			int mid = (left + right) / 2;
			if (nums[mid] > target ) {
				right = mid - 1;
				ans = mid;
			}
			else {
				left = mid + 1;
			}
		}
		return ans;
	}

	vector searchRange(vector& nums, int target) {
		int leftIdx =getLeftBorder(nums, target);
		int rightIdx = getRightBorder(nums, target) - 1;
		if (leftIdx <= rightIdx && rightIdx < nums.size() && nums[leftIdx] == target && nums[rightIdx] == target) {
			return vector{leftIdx, rightIdx};
		}
		return vector{-1, -1};
	}
};