博客

前提：是数组是有序的数据。

方法理论：二分查找的精髓就在不断折半查找需要的元素，让查找的元素落在正确的区间，二分的中心就是不断缩小区间，去查找正确的下标。

mid取值问题：mid=(left+right)/2,/2是向下取整，当left+right为奇数时，会取到区间的左边界，

对于查找相等的元素时，奇数和偶数不会有什么影响，代码如下1.1。

但是如果取到最后一个<=target值的时候，就需要+1向上取整，防止死循环，如1.2

结束条件：一般二分查找结束的条件是，left>right,即左边界大于右边界。但是如果查找最接近target的值 结束条件则是left==right.

//代码1.1 查找target
public int search(int[] nums, int target) {
        int l=0,r=nums.length-1;
        while(l<=r){
            int m=(l+r)/2;
            if(nums[m]<target){
                l=m+1;
            }else if(nums[m]>target){
                r=m-1;
            }else{
                return m;
            }
        }    
        return -1;
        
    }

//代码1.2 查找最后一个<=target的元素
public int search(int[] nums, int target) {
        //-1 表示不合法
           int l=-1,r=nums.length-1;
        while(l<r){
            //+1 向上取整 防止死循环
            int m=(l+r+1)/2;
            //满足条件的区间
            if(nums[m]<=target){
                l=m+1;
            }else{
            //  不满足条件的区间
               r=m-1;
            }
        }    
        return l;

    }

//代码1.3 查找最小>=target的值
public int search(int[] nums, int target) {
        //n 表示不合法
           int l=0,r=nums.length;
        while(l<r){
            //向下取整就行
            int m=(l+r)/2;
            //满足条件的区间
            if(nums[m]>=target){
                r=m;
            }else{
            //  不满足条件的区间
               l=m+1;
            }
        }    
        return r;

    }