普通二分
- 思路：逐渐缩小区间，直到找到，或者找不到，跳出循环
int l=0; int r=arr.length-1; int mid=0; while(l<=r) { mid=l+((r-l)>>1); if(arr[mid]==value) return mid; else if(arr[mid]>value) r=mid-1; else l=mid+1; } return -1;
有重复元素的二分
取第一个
- 当遇到arr[mid]==value时，不跳出循环，左区间不动，右区间会逐渐缩小
- mid=l+((r-l)>>1)本身自动向下取整，举例 l=k,r=k+1，(l+r)/2=k,mid值会逐渐向左区间靠近，左区间不动区间，因此右区间逐渐缩小，最后l==r
int l=0; int r=arr.length-1; int mid=0; while(l<r) { mid=l+((r-l)>>1); if(arr[mid]>=value) r=mid; else l=mid+1; } if(arr[l]==value) return l; else return -1;
取最后一个
- 当遇到arr[mid]==value时，不跳出循环，右区间不动，左区间会逐渐缩小
- mid=l+((r-l+1)>>1);向上取整，举例 l=k,r=k+1，(l+r+1)/2=k+1,mid值会逐渐向右区间靠近，左区间不懂区间，因此左区间逐渐缩小，最后l==r
int l=0; int r=arr.length-1; int mid=0; while(l<r) { mid=l+((r-l+1)>>1);//向上取整 if(arr[mid]>value) r=mid-1; else l=mid; } if(arr[l]==value) return l; else return -1;
时间复杂度
O（logn）
