二分查找算法实现（Java）二分查找简介算法实现

100 阅读 0 评论 66 点赞

我是靠谱客的博主背后冬日，这篇文章主要介绍二分查找算法实现（Java）二分查找简介算法实现，现在分享给大家，希望可以做个参考。

二分查找简介

二分查找又称折半查找，它是一种效率较高的查找方法。

二分查找的要求：

必须采用顺序存储结构。
必须按关键字大小有序排列。

原理

将数组分成3个部分，依次是：中值前、中值（数组中间位置的那个值）、中值后。将要查找的值和数组的中值进行比较，如果等于中值则直接返回，如果小于中值，则在中值前查找，如果大于中值，则在中值后查找。然后依次递归，将前半部分或后半部分继续分解为3部分进行查找。直到找到为止。

复杂度

假使总共有n个元素，那么二分后每次查找的区间大小就是n，n/2，n/4，…，n/2^k（接下来操作元素的剩余个数），其中k就是循环的次数。

最坏的情况是K次二分之后,每个区间的大小为1,找到想要的元素令n/2^k=1，可得k=log2n,（是以2为底，n的对数），但是在表示时间复杂度时，对数的底数可以忽略，所以，二分查找的时间复杂度为O(logn)。

递归实现的二分查找空间复杂度是O(logn);非递归的空间复杂度是O(1)。

算法实现

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
    public static int binarySearch(int[] arr, int value) {
        int s = 0;
        int e = arr.length - 1;
        int m;
        while (s <= e) {
            m = s + e >>> 1;
            if (arr[m] == value) {
                return m;
            } else if (arr[m] > value) {
                e = m - 1;
            } else {
                s = m + 1;
            }
        }
        return -1;
    }