二分查找，也称为折半查找，是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。我们应该如何用在具体问题中呢？
题目链接（力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台）
可以直接通过遍历一次数组就得到对应值下标了，时间复杂度为
。但是我们可以通过划分区间的方式获得更优秀的时间复杂度（二分查找），通过取中值的方式可以把一个数组划分出两个区间，通过中值可以判断出target在哪一个区间，循环迭代即可。按照这种方式我们可以一次舍去一整片区间，相比于遍历数组一次舍去一个数值，得到的时间复杂度为
。
具体细节见代码：
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size()-1;
while(left <= right){
int mid = (left + right)/2;
if(nums[mid] > target) //要查找的目标值在左区间
right = mid - 1;
else if(nums[mid] < target) //要查找的目标值在右区间
left = mid + 1;
else
return mid;
}
return -1;
}题目链接（力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 ）
我们依旧可以通过一次遍历完成，定义两个指针分别记住target值的第一次出现的下标，第二个指针记住target值最后一次出现的下标即可，时间复杂度为
。题目要求时间复杂度为
，我们采用上面这种二分查找算法会有一些问题，因为如果我们有一个数组
nums = [5, 5, 5, 5, 5, 5 ,5], target = 5 ，我们获得的mid既不知道开头下标也不知道结尾下标。也就是说，当mid等于target值的时候，我们需要额外做一些事情。
具体细节见代码：
vector<int> searchRange(vector<int>& nums, int target) {
if(nums.size() == 0)
return {-1, -1};
int begin = 0, end = 0;
//处理begin
int left = 0, right = nums.size()-1;
while(left < right){
int mid = (left + right)/2;
if(nums[mid] < target) //目标值在右区间
left = mid + 1;
else
right = mid;
}
if(nums[left] != target)
return {-1, -1};
else
begin = left;
//处理end
left = 0, right = nums.size()-1;
while(left < right){
int mid = (left + right + 1)/2;
if(nums[mid] <= target) //目标值在右区间
left = mid;
else
right = mid - 1;
}
end = right;
return {begin, end};
}所以不管是区间还是单个元素的问题，我们可以总结一个通用的模版：
处理区间左端点：
int left = 0, right = nums.size()-1;
while(left < right){
int mid = (left + right)/2;
if(nums[mid] < target)
left = mid + 1;
else
right = mid;
}通过 nums[mid] < target 这个条件来不断逼近目标值区间的左端点，最终left和right一起指向目标值区间的左端点。
处理区间右端点：
int left = 0, right = nums.size()-1;
while(left < right){
int mid = (left + right + 1)/2;
if(nums[mid] <= target)
left = mid;
else
right = mid - 1;
}通过 nums[mid] > target 这个条件来不断逼近目标值区间的右端点，最终left和right一起指向目标值区间的右端点。
注意：
1. 为什么在while循环的时候我们判断条件使用的是 left < right 而不是 left <= right 呢？
以处理目标值区间的左端点为例：
根据if else里的条件，left只会在target的左边的区间内移动，不会越过target，也就是说left可以移动到的最右边的位置正好是target的开始位置（如果符合条件的target只有一个，则就是这个元素的位置）；
right同理，也会在右边的区间移动，不会越过target，right可以移动到的最左边的位置正好是target的结束位置（如果符合条件的target只有一个，则就是这个元素的位置）；
根据以上两点分析，当 left = right 的时候一定是最终结果，要么是target的位置，要么就是无解。如果我们使用的是 left <= right ，当 left = right 的时候还会继续进入循环，循环没有突破边界的可能（即不可能出现left > right的可能），程序就会死循环。
2. 在求中点的时候要向下取整，避免在极端情况下（如果向上取整的话，如果此刻三个下标的位置是nums = [..., left, mid 和 right, ... ]，如果下一次循环依旧是更新right的话，三个下标的位置还是nums = [..., left, mid 和 right, ... ]）程序进入死循环。同理，在处理右端点的时候需要向上取整。
