二分查找是一种时间复杂度为O(logn)的查找算法

• 使用场景

  • 首先，二分查找依赖的是顺序表结构，简单点说就是数组。

  • 其次，二分查找针对的是有序数据。

    • 所以，二分查找只能用在插入、删除操作不频繁，一次排序多次查找的场景中。

  • 再次，数据量太小不适合二分查找。

    • 如果要处理的数据量很小，完全没有必要用二分查找，顺序遍历就足够了

  • 最后，数据量太大也不适合二分查找。

    ​ 二分查找的底层需要依赖数组这种数据结构，而数组为了支持随机访问的特性，要求内存空间连续，对内存的要求比较苛刻。比如，我们有 1GB 大小的数据，如果希望用数组来存储，那就需要 1GB 的连续内存空间。

    ​ 而我们的二分查找是作用在数组这种数据结构之上的，所以太大的数据用数组存储就比较吃力了，也就不能用二分查找了。

  • 更适用于近似查找

    ​ **“值等于给定值”的二分查找 **------凡是用二分查找能解决的，绝大部分我们更倾向于用散列表或者二叉查找树。

    ​ 二分查找更适合用在“近似”查找问题，在这类问题上，二分查找的优势更加明显。比如今天讲的这几种变体问题，用其他数据结构，比如散列表、二叉树，就比较难实现了。

一般二分查找

==数组中的数组单调递增==——{1,2,3,4,5,6}

public int search(int[] nums, int target) {
    int high=nums.length-1;
    int low=0;

    while(low<=high){ //这里要带等号
        //防止溢出，右移一位表示除2
        int mid=low+((high-low)>>1);
        if(target>nums[mid]){ //右边查
            low=mid+1;
        }else if(target<nums[mid]){ //左边查
            high=mid-1;
        }
        else{//查到了
            return mid;
        }
    }
    return -1;
}

变体二分查找

==数组中数据的单调不减==——{1,3,4,5,6,6,6,7,8}

• 查找第一个等于给定值的元素

//*查找第一个等于给定值的元素
public int findFirstEqual(int[] nums,int target) {
    int high=nums.length-1;
    int low=0;

    while(low<=high){ //这里要带等号
        //            int mid=(low+high)/2;
        int mid=low+((high-low)>>1);
        if(target>nums[mid]){ //右边查
            low=mid+1;
        }else if(target<nums[mid]){ //左边查
            high=mid-1;
        }else {//--相等继续查
            //mid 在最左侧 或者 mid左侧不等于target即停止，，否则一直查
            if (mid == 0 || nums[mid - 1] !=target) return mid;
            else high = mid - 1;
        }
    }
    return -1;
}

• 查找最后一个等于给定值的元素

//* 查找最后一个等于给定值的元素
public int findLastEqual(int[] nums,int target) {
    int high=nums.length-1;
    int low=0;

    while(low<=high){ //这里要带等号
        //            int mid=(low+high)/2;
        int mid=low+((high-low)>>1);
        if(target>nums[mid]){ //右边查
            low=mid+1;
        }else if(target<nums[mid]){ //左边查
            high=mid-1;
        }else {//--相等继续查
            //mid 在最右侧 或者 mid右侧不等于target即停止，，否则一直查
            if (mid == nums.length-1 || nums[mid + 1] !=target) return mid;
            else low=mid+1;
        }
    }
    return -1;
}

• 查找第一个大于等于给定值的元素

//* 查找第一个大于等于给定值的元素
public int findFirstHigher(int[] nums,int target) {
    int high=nums.length-1;
    int low=0;

    while(low<=high){ //这里要带等号
        //            int mid=(low+high)/2;
        int mid=low+((high-low)>>1);
        if(target>nums[mid]){ //右边查
            low=mid+1;
        }else if(target<=nums[mid]){ //左边查
            if (mid == 0 || nums[mid - 1] < target) return mid;
            else high=mid-1;
        }
    }
    return -1;
}

• 查找最后一个小于等于给定值的元素

//* 查找最后一个小于等于给定值的元素
public int findLastLower(int[] nums,int target) {
    int high=nums.length-1;
    int low=0;

    while(low<=high){ //这里要带等号
        //            int mid=(low+high)/2;
        int mid=low+((high-low)>>1);
        if(target>=nums[mid]){ //右边查
            if (mid == nums.length-1 || nums[mid + 1] > target) return mid;
            else low=mid+1;
        }else if(target<nums[mid]){ //左边查
            high=mid-1;
        }
    }
    return -1;
}