二分查找的变种(Java达成)

平凡二分查找:

先想起一下常备的二分查找

小心:二分查找有那般一个难题:当数组中数有再度时,比如
{3,3,3,3} 那些数组,二分查找3时,重返的是arr[1],也就是说二分查找并不会回去3先是次面世的地点0。

public class BinarySearch {
    public static <T extends Comparable<? super T>> int search(T arr[], T value) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = (left & right) + ((left ^ right) >> 1);
            if (arr[mid].compareTo(value) == 0) {
                return mid;
            } else if (arr[mid].compareTo(value) > 0) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Integer[] arr = new Integer[]{1, 3, 3, 6, 7, 9};

        //-1
        System.out.println(search(arr, 0));

        //0
        System.out.println(search(arr, 1));

        //5
        System.out.println(search(arr, 9));

        //-1
        System.out.println(search(arr, 10));

        //2
        System.out.println(search(arr, 3));
    }
} 

二分变种:findFirst函数

在一般二分查找中,在[left….right]左闭右闭区间中检索,假设找到了值为value的因素就认为找到了。而在那些findFirst函数中就不是这么,在[left….right]左闭右闭区间中搜寻,当找到值等于value的因素后,不是让right
= mid – 1,而是让right =
mid,继续在[left….right]左闭右闭区间中寻找。最终left== right时就淡出循环。

脱离循环后恐怕找到了value值,也有可能是循环遍历完全部数组后都没找到value,而退出循环。

由此退出循环后还要在认清一下是那种景况。

public class BinarySearch {
    public static <T extends Comparable<? super T>> int findFirst(T arr[], T value) {
        int left = 0;
        int right = arr.length - 1;
        //当left>=right时退出,这里的“=”情况与二分不同
        while (left < right) {
            int mid = (left + right) >> 1;
            if (arr[mid].compareTo(value) < 0) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        // 上面循环遍历完后。是找到了value值?还是没找到value值?判断一下。
        if (arr[left] == value) {
            return left;
        } else {
            return -1;
        }
    }

    public static void main(String[] args) {
        Integer[] arr = new Integer[]{1, 3, 3, 3, 3, 3, 3, 3, 3, 3, 6, 7, 9};

        //-1
        System.out.println(findFirst(arr, 0));

        //0
        System.out.println(findFirst(arr, 1));

        //12
        System.out.println(findFirst(arr, 9));

        //-1
        System.out.println(findFirst(arr, 10));

        //1
        System.out.println(findFirst(arr, 3));
    }
}

二分变种:fewer函数

介绍

给定一个数组,和一个变量value,从数组中找出值最接近value值而且比value小的那一个数。比如 arr
= {11,22,22,33 ,33,33,44,54}   value = 33。
22最接近value,而且比value小。

故而答案是2  ( 22在数组arr中的下角标 )  。

一经没找到比value小的数,那么输出 -1。

缓解思路

用二分查找方法。每回用 arr[mid]
来与value举行比对。小、等于,去左边找;大,去入手找。可能上一句的“等于”的情形你不太了解。普通二分查找是找出arr[mid]
== value,而fewer函数是为着找出比value小的数,所以即使arr[mid] ==
value,还得继续去右边找更小的值。

例子

图片 1

代码

public class BinarySearch {
    public static <T extends Comparable<? super T>> int fewer(T arr[], T value) {
        int left = 0;
        int right = arr.length - 1;
        //当left > right 时退出
        while (left <= right) {
            int mid = (left & right) + ((left ^ right) >> 1);
            if (value.compareTo(arr[mid]) <= 0) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return right;
    }

    public static void main(String[] args) {
        Integer[] arrF = new Integer[]{21, 23, 25, 25, 31, 34, 37, 39, 52, 63};

        //3
        System.out.println(fewer(arrF, 30));
    }
} 

二分变种:greater函数

相关文章