二分查找法

Question

如题所述

Answer 1

二分查找法的解释如下：

二分查找法也称折半查找法，是一种在有序数组中查找某一特定元素的搜索算法。我们可以从定义可知，运用二分搜索的前提是数组必须是有序的，这里需要注意的是，我们的输入不一定是数组，也可以是数组中某一区间的起始位置和终止位置。

如果想要在数组中查找一个数，最基本的方法就是暴力解法：一次遍历，这时候时间复杂度是O（N），二分查找就是其中的一种优化，时间复杂度是O（logN）；具体做法是一步一步逼近直到找到。前提是数组需要是一个排序数组。

查找过程：

首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功。

否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。

重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

算法要求：

1、必须采用顺序存储结构。

2、必须按关键字大小有序排列。

 

比较次数

计算公式：

当顺序表有n个关键字时：

查找失败时，至少比较a次关键字；查找成功时，最多比较关键字次数是b。

注意：a，b，n均为正整数。