二分查找


二分查找是针对有序数组进行查找的一种算法,算法复杂度是 O(logn)。

将目标元素与数组的中间元素比较,小于中间元素则说明其在前半部分数组中,对前半部分重新执行二分查找;同理如果大于中间元素则在后半部分重新执行二分查找;相等直接返回当前下标即可(注意中间元素已经比较过,递归的过程中不需要再包含)。显然这是一个迭代或者递归的过程,代码实现也分为两种方式,迭代实现和递归实现。

迭代实现代码示例:

public static int binarySearch(int[] arr, int key) {
    if (arr == null || arr.length == 0)
        return -1;
    int low = 0;
    int hign = arr.length - 1;
    while (low <= hign) {
        int mid = (low + hign) / 2;
        if (arr[mid] > key) {
            hign = mid - 1;
        } else if (arr[mid] < key) {
            low = mid + 1;
        } else {
            return mid;
        }
    }
    return -1;
}

递归实现如下所示

public static int binarySearchRecursively(int[] arr, int key, int low, int hign) {
    if (low > hign)
        return -1;
    int mid = (low + hign) / 2;
    if (arr[mid] == key) {
        return mid;
    } else if (arr[mid] < key) {
        return binarySearchRecursively(arr, key, mid + 1, hign);
    } else {
        return binarySearchRecursively(arr, key, low, mid - 1);
    }
}

两种方式都 ok 主要看个人喜好,一般情况下迭代方式会相对更友好一些,因为递归总是要占用更多的栈空间,有引发 StackOverflowException 的风险。像 int index = Arrays.binarySearch(sortedArray, key); 方法中默认就使用了迭代方式而非递归方式。

和线性查找比起来,理论上二分查找效率呀更高一些,但是也看具体情况。二分查找需要先对数组进行排序而线性查找则不需要,如果要找的数比较小的情况下线性查找的次数也要比二分查找更少。因此在实际使用中还需要针对具体场景进行选择。

参考

Copyright © jverson.com 2019 all right reserved,powered by Gitbook 21:04:41

results matching ""

    No results matching ""