使用前提:满足单调性.
int left = 0;
int right = n-1;
while(left<=right)
{
int mid = (left+right)>>1;//这样可以正确地处理负数
if(arr[mid]<k)
{
left = mid+1;
}
else if(arr[mid]>k)
{
right = mid-1;
}
else
return mid;
}
//如果没有搜索到,那么走到这时候l和r的值是这个元素在应该插入到该有序数组到位置.(leetCode 35)
这里的处理思想很简单,就是纯粹的闭区间[left,right].如果k在mid右边,那么就从[mid+1,right]开始找(由于mid肯定不是答案,那么就从mid+1开始找).
这是最最常用的.适合找到的数是唯一解的情况.
（ps：上面似乎返回l才对）
循环条件是 while (l <= r)，这意味着当循环结束时，l 一定大于 r，具体来说是 l = r + 1**r (右指针)**：会停留在 “比目标值小的元素中，最右边的那一个” 的下标位置。
l (左指针)：会停留在 “比目标值大的元素中，最左边的那一个” 的下标位置。
插入位置的定义是：如果目标值不存在，需要把它按顺序插入。这意味着它应该插在“比它小的数”后面，或者“比它大的数”也就是“第一个大于它的数”的位置（把原来的数向后挤）。
r 指向的是“比它小的数”，所以插入位置应该是 r + 1。l = r + 1，所以 l 恰好就是正确的插入位置。最典型的用法就是LeetCode 34 在排序数组查找元素的第一个和最后一个位置
题目的大意其实是:如果有1111111112222222222233333333这样的数组,如何找到第一个2和最后一个2的位置?
原题:
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
解答:
vector<int> searchRange(vector<int>& nums, int target)
{
if(nums.size()==0)return {-1,-1};
int l = 0,r = nums.size()-1;
//找左边第一个 可能的答案区间是[l,r)
while(l<r)
{
int mid = (l+r)>>1;
if(nums[mid]>=target)r = mid;
else l = mid+1;
}
int leftPos = l;
if(nums[l]!=target)return {-1,-1};
l = 0,r = nums.size()-1;
//找右边的第一个 可能的答案区间是(l,r]
while(l<r)
{
int mid = (l+r+1)>>1;
if(nums[mid]<=target)l = mid;
else r = mid - 1;
}
if(nums[l]!=target)return {-1,-1};
return {leftPos,l};
}
模板的记忆:
if(check(mid))后面接的是l,那么int mid时就需要+1.check(mid)往往取的是等号.提供一个一脉相承更加优雅的思路：
public int[] searchRange(int[] nums, int target) {
if(nums==null||nums.length==0)return new int[]{-1,-1};
int l = 0;
int r = nums.length-1;
while(l<=r){
int mid = (l+r)/2;
if(nums[mid]>=target){
r = mid-1;
}
else if(nums[mid]<target){
l = mid+1;
}
}
if(l<0||l>=nums.length||nums[l]!=target)return new int[]{-1,-1};
int ansl = l;
l = 0;
r = nums.length-1;
while(l<=r){
int mid = (l+r)/2;
if(nums[mid]>target){
r = mid-1;
}
else if(nums[mid]<=target){
l = mid+1;
}
}
int ansr = r;
return new int[]{ansl,ansr};
}
这个思路要比前面好理解的多，也是左闭右闭区间的思路。
一开始要找起点，那么就在nums[mid]==target的时候我们把r往左收缩；
停下来的时候，仍然遵循l在r的右边，按照图想象一下，（同时l=r+1），那么r就停在了第一个target的左边一个位置，l就是起点
类似的，找终点的时候，在nums[mid]==target的时候把l往右收缩；
停下来的时候，l在r的右边，l=r+1，那么r就停在了最后一个target的位置，l是下一个位置。
同时注意在一开始我们判断了一下，如果l越界或者nums[l]!=target，说明数组中没有target，直接返回{-1,-1}。
另外，开头最好判读数组是否为0和长度是否为0