ncre数据结构与算法

16 基本查找算法：二分查找算法

2020-02-18  本文已影响0人  GoFuncChan

二分查找算法

原理

二分查找算法也叫折半法查找法，要求待查找的列表必须是按关键字大小有序排列的顺序表。
查找过程如下所示：
（1）将表中间位置记录的关键字与查找关键字比较，如果两者相等则表示查找成功；否则利用中间位置记录将表分成前、后两个子表。
（2）如果中间位置记录的关键字大于查找关键字，则进一步查找前一个子表，否则查找后一个子表。
（3）重复以上过程，一直到找到满足条件的记录为止时表明查找成功。
（4）如果最终子表不存在，则表明查找不成功。

性能分析

接下来用平均查找长度来分析二分查找算法的性能，我们可以使用一个被称为判定树的二叉树来描述二分查找过程。首先验证树中的每一个节点对应表中的一个记录，但是节点值不是用来记录关键字的，而是用于记录在表中的位置序号的。根节点对应当前区间的中间记录，左子树对应前一个子表，右子树对应后一个子表。当折半查找成功时，关键字的比较次数不会超过判定树的深度。因为判定树的叶节点和所在层次的差是1，所以n个节点的判定树的深度与n个节点的完全二叉树的深度相等，都是(log2 n)+1。这样，折半查找成功时，关键字比较次数最多不超过(log2 n)+1。相应地，当折半查找失败时，其整个过程对应判定树中从根节点到某个含空指针的节点的路径。所以当折半查找成功时，关键字比较次数也不会超过判定树的深度(log2 n)+1。可以假设表的长n=2h -1，相应的判定树一定是深度为h的满二叉树，log2 (n+1)。在此假设将长度为n的表分成b块，每块含有s个元素，即b=n/s。又假设每个记录的查找概率相等，则折半查找成功时的平均查找长度为：

二分查找算法性能分析.png

二分查找方法具有比较次数少、查找速度快及平均性能好的优点。缺点是要求待查表为有序表，且插入、删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。

算法实现
说明：

元素必须是有序的，如果是无序的则要先进行排序操作。

基本思想：

二分查找基于分治思想，在实现上可以使用递归或迭代，首先用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。

复杂度分析：
最坏情况下，关键词比较次数为log2(n+1)，且期望时间复杂度为O(log2n)；

注：二分查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，二分查找能得到不错的效率。
但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。

Go语言描述

最简单的版本：即序列中忽略重复元素的位置情况：

// 迭代版本
func BinarySearch1(arr []int, v int) int {
    start, end := 0, len(arr)-1
    for start <= end {
        mid := start + (end-start) / 2
        // fmt.Println("mid:",mid)
        if arr[mid] == v {
            return mid
        } else if arr[mid] > v {
            // 左边
            end = mid - 1
        } else {
            // 右边
            start = mid + 1
        }
    }

    return -1
}

// 递归版本
func BinarySearch2(arr []int, v, start, end int) int {
    if start <= end {
        mid := (start + end) / 2
        // fmt.Println("mid:",mid)
        if arr[mid] == v {
            // 找到
            return mid
        } else if arr[mid] > v {
            // 左边递归
            return BinarySearch2(arr, v, start, mid-1)
        } else {
            // 右边递归
            return BinarySearch2(arr, v, mid+1, end)
        }
    }
    return -1
}
二分查找算法的变体

以上的算法实现是没考虑重复元素的严格情况的，如需考虑重复元素且返回特定的索引，有以下变体：

变体一：查找第一个值等于给定值的元素
// 变体一：查找第一个值等于给定值的元素
func BinarySearch3(arr []int, v int) int {
    start, end := 0, len(arr)-1
    for start <= end {
        mid := start + (end-start)/2
        // fmt.Println("mid:",mid)
        if arr[mid] == v {
            if mid == 0 || arr[mid-1] != v {
                return mid
            } else {
                end = mid - 1
            }
        } else if arr[mid] > v {
            // 左边
            end = mid - 1
        } else {
            // 右边
            start = mid + 1
        }
    }

    return -1
}
变体二：查找最后一个值等于给定值的元素
// 变体二：查找最后一个值等于给定值的元素
func BinarySearch4(arr []int, v int) int {
    start, end := 0, len(arr)-1
    for start <= end {
        mid := start + (end-start)/2
        if arr[mid] == v {
            if mid == end || arr[mid+1] != v {
                return mid
            } else {
                end = mid - 1
            }
        } else if arr[mid] > v {
            // 左边
            end = mid - 1
        } else {
            // 右边
            start = mid + 1
        }
    }

    return -1
}

关于二分查找算法的局限性

二分查找的时间复杂度是O(logn)，查找数据的效率非常高。不过，并不是什么情况下都可以用二分查找，它的应用场景是有很大局限性的。那 什么情况下适合用二分查找，什么情况下不适合呢?

上一篇下一篇

猜你喜欢

热点阅读