欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Java 实现二分查找 (详细) / 二分查找与普通查找的效率

程序员文章站 2022-03-14 23:47:32
...

1 二分查找的实现

1.1 二分查找思路

  首先,二分查找是针对有序数组进行,升序降序都可。
  方法是,先找到这组有序数组的中间值,然后将要找的元素与中间值进行比较:
如果比中间值小,则把中间后面的 ” 砍掉 “,再在前半段找中间值,判断要找元素与中间值的大小,重复上述操作直至找到制定元素;
如果比中间值大,则把中间值前面的 ” 砍掉 “,在前半段找中间值,判断要找元素与中间值的大小,重复上述操作直至找到制定元素。

1.2 具体实施

(1) 首先,明确我们要找到中间值,是不只是一开始整个数组的中间值,还有每次砍掉一部分之后的中间值,中间值是在不断变化的。要找中间值,就要找到当前步骤的最左边的位置和最右边的位置。
  用索引来表示,最初的最左就是0 ,最初的最右就是a.length -1

    int left = 0;
    int right = a.length-1; 
    int mid = (left + right) / 2;

(2) 接着,我们要写一个循环,不断比较要找的元素与中间元素的大小,因为中间元素会随着数组长短的变化而变化,所以将中间元素的计算放在循环内。循环的前提是左右位置没有越界,左位置在右位置的左边,即索引的位置 left <= right
 当要找元素大于中间元素,则砍去左边部分(当前中间值mid的左边部分),将最左边的序号调整至原来mid 的右侧,即 mid + 1 的位置;
 当要找元素小于中间元素,则砍去右边部分(当前中间值mid的右边部分),将最右边的序号调整至原来mid 的左侧,即 mid - 1 的位置。
 最后,mid 位置的数和要找的元素一样时,找到了指定元素,就返回这个数的位置,即返回 mid

while (left <= right ) {
        int mid = (left + right) / 2;
        if( toSearch > a[mid] ){
            left = mid + 1;
        }else if( toSearch < a[mid]){
            right = mid -1;
        }else{
            return mid;
        }
    }

注意:
  left、right、mid 都是位置,而我们要找的元素toSearch 与每个位置上的数进行比较,不要用位置和数进行比较。

1.3 完整代码

public static int binarySearch(int[] a, int toSearch) {
    int left = 0;
    int right = a.length-1;
    while (left <= right ) {
        int mid = (left + right) / 2;
        if( toSearch > a[mid] ){
            left = mid + 1;
        }else if( toSearch < a[mid]){
            right = mid -1;
        }else{
            return mid;
        }
    }
    System.out.println("找不到该数。");
    return -1;
}

2 二分查找与普通查找效率比较

比较两种查找的循环执行次数:
(1) 首先,我们要创建一个比较大的数组,这样有利于我们观察出,究竟哪种方法的效率高,写一个方法创建一个非常大的有序数组,有10000个元素的数组。

public static int[] makeBigArray(){
    int[] a = new int[10000];
    for (int i = 0; i <a.length ; i++) {
        a[i] = i;
    }
    return a;
}

(2) 接着,在代码的如下 1、2 处增加计数,3、4 处输出结果,找到或是找不到都得输出结果,让我们得知循环了多少次。

public static int binarySearch(int[] a, int toSearch) {
    int count = 0;                      //  1
    int left = 0;
    int right = a.length - 1;
    while (left <= right ) {
        count++;                        //  2
        int mid = (left + right) / 2;
        if( toSearch > a[mid] ){
            left = mid + 1;
        }else if( toSearch < a[mid]){
            right = mid -1;
        }else{
            System.out.println("count:" + count);//  3
            return mid;
        }
    }
    System.out.println("count:" + count);    //   4
    return -1;
}

(3) 我们采用的例子是在0~9999 这10000 个元素中查找9999 ,若是采用普通查找,一个一个进行比较,会进行10000次的比较,而用二分查找则是 14 次。

int[] a = makeBigArray();
int pos = binarySearch(a,9999);
System.out.println(pos);

Java 实现二分查找 (详细) / 二分查找与普通查找的效率
  可以看出二分查找的效率更高,多想一想必然是如此的,因为它每次比较一次就会砍掉当前长度的一半,可以想象为对数函数的曲线,横轴为数组的元素个数,纵轴为循环执行次数,当横轴变得很大时,纵轴上升幅度依旧不大。