题目
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
进阶：你可以设计并实现时间复杂度为 O ( log n ) O(\log n)O(logn) 的算法解决此问题吗？
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：
输入：nums = [], target = 0
输出：[-1,-1]
#思路
解题思想
本题有四种情况
1.目标值不在有序数组范围内，比数组中的所有的元素都还要小
2.目标值不在有序数组范围内，比数组中的所有的元素都还要大
3.目标值在有序数组范围内，且存在于有序数组内部
4.目标值在有序数组范围内，不存在有序数组内部
在代码这种主函数第一个if解决1和2问题，else if 解决第三个问题，else解决第4个问题
#include<iostream> #include<vector> using namespace std; vector<int>a; int leftbroder(vector<int>&nums,int targer) { int left = 0; int right = nums.size()-1; int leftb=-2; while(left<=right) { int middle = (left+right)/2; if(nums[middle]>=targer) { right=middle-1; leftb = right; } else { left=middle+1; } } return leftb; } int rightbroder(vector<int>&nums,int targer) { int left = 0; int right = nums.size()-1; int rightb=-2; while(left<=right) { int middle = (left+right)/2; if(nums[middle]>targer) { right=middle-1; } else { left=middle+1; rightb = left; } } return rightb; } int main() { int tar,n; while(1) { cin>>n; a.push_back(n); if(cin.get()=='\n') { break; } } cin >> tar; int r,l; //获取右边界 r = rightbroder(a,tar); // 获取左边界 l = leftbroder(a,tar); if(l==-2||r==-2)cout << "-1" << "-1";//当在有序数组范围之外的时候便一定存在左边界或者有边界都为-2的情况，因为必有一种边界随着二分查找而没有发生变化，可以自己推导一下。 else if(r-l>1)cout << l+1 << r-1; else { cout << "-1" << "-1"; } return 0; }
第二种解题思想
在判断中间值相同的时候去判断左边界跟右边界
#include<iostream> #include<vector> using namespace std; vector<int>a; int first_position(vector<int>&nums,int target) { int left = 0; int right = nums.size()-1; while(left <= right) { int mid = (left + right)/2; if(nums[mid]==target) { if(mid==0||nums[mid-1]<target)//在满足目标值=target的值的时候，并且同时满足为起始地址和前一个元素小于目标值便可以证明这个地方就是目标值的左边界 { return mid; } right = mid - 1; } else if(nums[mid]>target) { right = mid -1 ; } else if(nums[mid]<target) { left = mid + 1; } } return -1; } int last_position(vector<int>&nums,int target) { int left = 0; int right = nums.size()-1; while(left<=right) { int mid = (left+right)/2; if(nums[mid]==target) { if(mid==nums.size()-1||nums[mid+1]>target) { return mid; } left = mid+1; } else if(nums[mid]>target) { right = mid -1 ; } else if(nums[mid]<target) { left = mid + 1; } } return -1; } int main() { int tar,n; while(1) { cin>>n; a.push_back(n); if(cin.get()=='\n') { break; } } cin >> tar; int r,l; //获取右边界 r = last_position(a,tar); // 获取左边界 l = first_position(a,tar); cout << l << r; return 0; }
