1.題目

難點：要求時間復雜度度為O(logn)。

2.算法思路

需要找到左邊界和右邊界就可以解決問題。

題目中的數組具有“二段性”，所以可以通過二分查找的思想進行解題。

代碼：

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {int left1=0,right1=nums.size()-1;vector<int> v;if(nums.size()==0) return {-1,-1};//處理邊界情況//找左邊界while(left1<right1){int mid=left1+(right1-left1)/2;if(nums[mid]<target) left1=mid+1;if(nums[mid]>=target) right1=mid;}if(nums[left1]==target) v.push_back(left1);else return {-1,-1};//找右邊界int left2=0,right2=nums.size()-1;while(left2<right2){int mid=left2+(right2-left2+1)/2;if(nums[mid]<=target) left2=mid;if(nums[mid]>target) right2=mid-1;}if(nums[left2]==target) v.push_back(left2);return v;}
};

細節問題：

首先考慮邊界情況，數組為空先判斷一下。

然后就是循環條件不能寫等于，否則mid始終等于right(找左邊界時)/left（找右邊界時），會死循環。

還有找左邊界時，mid要向下取整，找有邊界時，mid要像上取整。否則只剩兩個值時，mid始終等于right(找左邊界時)/left（找右邊界時），會死循環。

3.運行結果

4.總結二分查找的模板