34. Find First and Last Position of Element in Sorted Array + 二分
题意懒得抄了，大概是：在升序数组中给定整数target，找到第一个和最后一个target的索引，找到返回{index1， index2}，否则返回{-1， -1}；
时间复杂度要求:O(logn)
分析：要求对数时间，又是查找，我们不难想到二分查找。但是有一点，怎么查到第一个和最后一个呢？这困扰了我。
算法：来自leetcode caikehe
1. 使用二分变体，查找target作为index1，再找target+1， 作为index2；
2. 对index做判断，如果它未越界且它的对应值等于target则返回{index1， index2-1}；否则，返回{-1， -1}；
源码
class Solution { public: vector<int> searchRange(vector<int>& nums, int target) { //binary find int index1 = binarySearch(nums, target); int index2 = binarySearch(nums, target+1) - 1; if(index1 < nums.size() && nums[index1] == target) return {index1, index2}; return {-1, -1}; } //二分变体 int binarySearch(vector<int>& nums, int target) { int l = 0, r = nums.size()-1; while(l <= r) { int mid = l + (r-l)/2; if(nums[mid] < target) l = mid + 1; else r = mid -1; } return l; } };
查看5道真题和解析
