《代码随想录》-2.二分查找

前提：
1.有序
2.无重复

//版本1
int left=0;
int right=nums.size()-1；
while(left<=right){
  int middle=left+(right-left)/2;//防止溢出
  if(nums[middle]>target){
    right=milddle-1;}
  else if(nums[middle]<target{
    left=middle+1;}
  else{
    return middle;
  }
}
return -1;//没找到目标值

区间：
1.[left,right]
因为left==right有意义
==> right=nums.size()-1
==>while(left<=right)要用 <=
if(nums[middle]>right) 也就是目标值在左边，此时区间变成[left,middle-1] => right=middle-1

时间复杂度：O(logn)
【while循环次数：假设共n个数，区间大小为n,n/2,n/4.....n/(2^k)，
n/(2^k )>=1最坏的情况是每个区间大小为1，n/(2^k)=1，k=log2n】
空间复杂度：1

//版本2
int left=0;
int right=nums.size()；
while(left<right){
  int middle=left+(right-left)>>1;//>>是右移运算符，右移一位相当于除2，右移n位相当于除以2的n次方；mid=(left+right)>>1等价于mid=(left+right)/2
  if(nums[middle]>target){
    right=milddle;}
  else if(nums[middle]<target{
    left=middle+1;}
  else{
    return middle;
  }
}
return -1;//没找到目标值

区间：
1.[left,right)
因为left==right没有意义
==> right=nums.size()
==>while(left<right)要用 <
if(nums[middle]>right) 此时区间变成[left,middle） => right=middle
left的情况不变

时间复杂度：O(logn)
空间复杂度：1