Given an array of integers nums 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].
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
class Solution { public: int bs(vector<int> &n,int t) { int l=0,r=n.size()-1,m; while(l<=r) { m=(l+r)/2; if(n[m]<t) l=m+1; else r=m-1; } return l; } vector<int> searchRange(vector<int>& nums, int target) { int idx1=bs(nums,target); int idx2=bs(nums,target+1)-1; if(idx1<nums.size()&&nums[idx1]==target) return {idx1,idx2}; return {-1,-1}; } };
private static int lowerBound(int[] a, int low, int high, int element){ while(low < high){ int middle = low + (high - low)/2; if(element > a[middle]) low = middle + 1; else high = middle; } return low; } private static int upperBound(int[] a, int low, int high, int element){ while(low < high){ int middle = low + (high - low)/2; if(a[middle] > element) high = middle; else low = middle + 1; } return low; }
34. Find First and Last Position of Element in Sorted Array
原文：https://www.cnblogs.com/lychnis/p/11787815.html