Home Java面试 二分查找 算法

# 二分查找

二分查找（ binary search ），也称作折半查找（ half-interval search ），每次划分一半进行下一步搜索，所以时间复杂度无非就是 while 循环的次数！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//二分查找 Java 实现 （升序数组）
public static int binarySearch(Integer[] srcArray, int des) {
    int low = 0;
    int high = srcArray.length - 1;
 
    while ((low <= high) && (low <= srcArray.length - 1)
            && (high <= srcArray.length - 1)) {
            // >> 右移符号 表示除以 2
        int middle = (high + low) >> 1;
        if (des == srcArray[middle]) {
            return middle;
        // 如果要查找的值 小于最中间的值 就算选择 左边的区间
        } else if (des < srcArray[middle]) {
            high = middle - 1;
        } else {
            low = middle + 1;
        }
    }
    return -1;
}

# 时间复杂度

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

# 二分查找的缺点

虽然二分查找的效率高，但是要将表按关键字排序。而排序本身是一种很费时的运算。既使采用高效率的排序方法也要花费 O(nlgn) 的时间。

二分查找只适用顺序存储结构。为保持表的有序性，在顺序结构里插入和删除都必须移动大量的结点。因此，二分查找特别适用于那种一经建立就很少改动、而又经常需要查找的线性表。

对那些查找少而又经常需要改动的线性表，可采用链表作存储结构，进行顺序查找。链表上无法实现二分查找。

Edited on Views times