二分查找法(Binary Search)以及其变种floor和c

对于有序数列才能使用二分查找法(排序的作用)

基本思想:将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果x=a[n/2],则找到x,算法中止；如果x<a[n/2],则只要在数组a的左半部分继续搜索x,如果x>a[n/2],则只要在数组a的右半部搜索x.

一般的二分查找法

public class BinarySearch {

    /**
     * @param arr  传入的数组
     * @param n 数组的大小
     * @param target 需要查找的值
     * @return  返回的位置,如果没有找到就返回-1
     */
    static int binarySearch(int[] arr,int n,int target){
        //在arr[l..r]之中查找target
        int l = 0,r = n-1;
        while (l < r){

            //(l+r)/2会产生程序溢出的问题(其中一个值接近int的最大值的时候)
            int mid = l + (r-l)/2;
            if (arr[mid] == target){
                return mid;
            }

            if (target < arr[mid]){
                //在arr[l...mid-1]之中查找target
                r = mid - 1;
            }else {
                //在arr[mid+1..r]之中查找target
                l = mid + 1;
            }

        }
        return -1;
    }


    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,7,8,9};
        System.out.println(binarySearch(arr,arr.length,3));
    }

}

递归的二分查找法

对递归实现通常上思维更加简单,但是性能上会略差

/**
     * 二分查找的递归实现方式
     * @param arr  数组
     * @param left 数组的左边界
     * @param right 数组的右边界
     * @param target 目标值
     * @return
     */
    static int binarySearch2(int[] arr,int left,int right,int target){

        //在边界范围以内
        if (left < right){
            int mid = left+(right-left)/2;

            if(arr[mid] == target){
                return mid;
            }

            if (arr[mid] < target){
                return binarySearch2(arr,mid+1,right,target);
            }else {
                return binarySearch2(arr,left,mid-1,target);
            }
        }
        return -1;
    }

二分查找的变种形式

对于上述两种二分查找方式,当数组中存在重复元素的时候就会显得有些鸡肋,这里就引入了二分查找法的变种形式

• 当存在大量重复的元素时，floor找的是第一个，ceil找的是第一个。
• 当不存在指定的元素时，floor是比其小最大的一个，而ceil是比其大最小的一个。

public class BinarySearch2
{

    /**
     * 用于寻找目标值第一次出现的位置
     * @param arr 数组
     * @param target 目标值
     * @return 目标值第一次出现的位置,如果没有找到就是最接近目标值(左边)的位置
     */
    private static int floor(Comparable[] arr, Comparable target){

        //寻找比target小的最大索引(left设置为-1是因为有可能最左边的元素也有可能不是目标值)
        //与下面的right设置为arr.length是一样的性质
        int left = -1;
        int right = arr.length-1;

        while (left < right){

            int mid = left + (right - left+1)/2;
            //中间值大于目标值  选择左边区域
            if (arr[mid].compareTo(target) >= 0){
                right = mid - 1;
            }else {
                left = mid;
            }

        }


        // 如果该索引+1就是target本身, 该索引+1即为返回值
        if( left + 1 < arr.length && arr[left+1] == target ) {
            return left + 1;
        }


        // 否则, 该索引即为返回值
        return left;

    }

    /**
     * 用于寻找目标值最后一次出现的位置
     * @param arr 数组
     * @param target 目标值
     * @return 目标值第一次出现的位置,如果没有找到就是最接近目标值(右边)的位置
     */
    private static int ceil(Comparable[] arr,Comparable target){

        //寻找比target大的最小索引
         int left = 0;
         int right = arr.length;
         while (left < right){
             //注意与上面去中间值的区别
             int mid = left + (right - left)/2;
             //中间值小于目标值
             if( arr[mid].compareTo(target) <= 0 ){
                 left = mid + 1;
             }else {
                 right = mid - 1;
             }
         }

         //如果索引-1就是目标值本上,该索引+1就是返回值
         if (right - 1 >= 0 && arr[right-1] == target ){
             return right-1;
         }
         //否则这个索引就是返回值
         return right;
    }

    public static void main(String[] args) {
        Comparable[] arr = {1,1,2,3,5,5,5,5,9};
        System.out.println(floor(arr,0));
        System.out.println(ceil(arr,0));
    }

}

参考博客
GitHub源码