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

二分查找(binary search)java实现及时间复杂度

程序员文章站 2022-05-19 08:24:35
概述 在一个已排序的数组seq中,使用二分查找v,假如这个数组的范围是[low...high],我们要的v就在这个范围里。查找的方法是拿low到high的正中间的值,我们假设是m,来跟v相比,如果m>v,说明我们要查找的v在前数组seq的前半部,否则就在后半部。无论是在前半部还是后半部,将那部分再次 ......

概述

在一个已排序的数组seq中,使用二分查找v,假如这个数组的范围是[low...high],我们要的v就在这个范围里。查找的方法是拿low到high的正中间的值,我们假设是m,来跟v相比,如果m>v,说明我们要查找的v在前数组seq的前半部,否则就在后半部。无论是在前半部还是后半部,将那部分再次折半查找,重复这个过程,知道查找到v值所在的地方。
实现二分查找可以用循环,也可以递归。

java实现

循环

public static int iterativeSearch(int v, int[] seq) {
        int low = 0, high = seq.length - 1;
        while (low < high) {
            int mid = (low + high) / 2;
            int m = seq[mid];
            if (v == m) {
                return mid;
            } else if (v > m) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }
}

递归

public static int recursionSearch(int v, int low, int high, int[] seq) {
        if (low > high) return -1;
        int mid = (low + high) / 2;
        int m = seq[mid];
        if (v == m) {
            return mid;
        } else if (v > m) {
            return recursionSearch(v, mid + 1, high, seq);
        } else {
            return recursionSearch(v, low, mid - 1, seq);
        }
    }
}

java8原生实现

private static int binarySearch0(int[] a, int fromIndex, int toIndex,
                                     int key) {
        int low = fromIndex;
        int high = toIndex - 1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            int midVal = a[mid];

            if (midVal < key)
                low = mid + 1;
            else if (midVal > key)
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found.
    }

时间复杂度

比如:总共有n个元素,每次查找的区间大小就是n,n/2,n/4,…,n/2^k(接下来操作元素的剩余个数),其中k就是循环的次数。 
由于n/2^k取整后>=1,即令n/2^k=1, 
可得k=log2n,(是以2为底,n的对数),所以时间复杂度可以表示O()=O(logn)