题目：
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
解法一（二分查找）：
直接遍历所有数组nums中元素时间复杂度为O(n)，没有利用到数组升序排列的条件。由于数组已经排序，因此整个数组是单调递增的，我们可以利用二分法来加速查找的过程。创建函数最终返回结果result设置初始值为[-1, -1]，进行二分查找直至left和right两个指针找到指定target目标或者满足left和right关系的终止条件。若left和right找到指定target目标，则进行扩展直到搜索到指定元素的第一个和最后一个位置，如下为笔者实现的代码：
class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {vector<int> result;result.push_back(-1);result.push_back(-1);if(nums.empty()){return result;}int length = nums.size();int left = 0;int right = length-1;while(nums[(left+right)/2]!=target){if(nums[(left+right)/2]>target){right=(left+right)/2;}else if(nums[(left+right)/2]<target){left=(left+right)/2;}if(left+1>=right){if(nums[left]==target){result[0]=left;result[1]=left;return result;}if(nums[right]==target){result[0]=right;result[1]=right;return result;}return result;}}int left_new = (left+right)/2, right_new=(left+right)/2;while(left_new>0 && nums[left_new-1]==target){left_new--;}while(right_new<length-1 && nums[right_new+1]==target){right_new++;}result[0]=left_new;result[1]=right_new;return result;}
};由于利用了二分查找优化对升序数组的遍历过程，因此其时间复杂度为O(log n),符合题目给出要求的解题思路。
解法二（官方解题）：
官方解题方法与上述笔者所用思想相同，都是利用了二分法来加速对单调递增数组遍历查找的过程。考虑target开始和结束的位置，其实我们要找的是数组中[第一个等于taget的位置]（记为leftIdx）和[第一个大于target的位置减一]（记为rightIdx）。
二分查找中，寻找leftIdx即为在数组中寻找第一个大于等于target的下标，寻找rightIdx即为在数组中寻找第一个大于target的下标，然后将下标减一。两者的判断条件不同，为了代码的复用，我们定义binarySearch(nums, target, lower)表示在nums数组中二分查找target的位置，如果lower为true，则查找第一个大于等于target的下标，否则查找第一个大于target的下标。
最后，因为target可能不存在数组中，因此我们需要重新校验我们得到的两个下标leftIdx和rightIdx，看是否符号条件，如果符合条件就返回[leftIdx, rightIdx]，不符合就返回[-1, -1]。如下为实现的代码：
class Solution {
public:int binarySearch(vector<int>& nums, int target, bool lower) {int left = 0, right = (int)nums.size() - 1, ans = (int)nums.size();while (left <= right) {int mid = (left + right) / 2;if (nums[mid] > target || (lower && nums[mid] >= target)) {right = mid - 1;ans = mid;} else {left = mid + 1;}}return ans;}vector<int> searchRange(vector<int>& nums, int target) {int leftIdx = binarySearch(nums, target, true);int rightIdx = binarySearch(nums, target, false) - 1;if (leftIdx <= rightIdx && rightIdx < nums.size() && nums[leftIdx] == target && nums[rightIdx] == target) {return vector<int>{leftIdx, rightIdx};} return vector<int>{-1, -1};}
};时间复杂度： O(logn) ，其中 n 为数组的长度。二分查找的时间复杂度为 O(logn)，一共会执行两次，因此总时间复杂度为 O(logn)。空间复杂度：O(1) 。只需要常数空间存放若干变量。
笔者小记：
1、对于已经排列的单调递增数组，我们可以利用二分法来加速查找的过程，避免依次遍历所有数组元素【时间复杂度为O(n)】，利用二分法查找数组元素可将时间复杂度降低至O(logn)。