“查找”的版本间的差异

2022年9月21日 (三) 03:29的版本

顺序查找：将待查找的关键字跟表中的数据从头至尾按顺序进行比较。

平均查找长度（等概率情况）：

二分法查找（折半查找）的基本思想是：（设R[low,...,high]是当前的查找区）

（1）确定该区间的中点位置：mid=⌊(low+high)/2⌋（向下取整）；

（2）将待查的k值与R[mid].key比较，若相等，则查找成功并返回此位置，否则需确定新的查找区间，继续二分查找，具体方法如下。

若R[mid].key>k，则由表的有序性可知R[mid,...,n].key均大于k，因此若表中存在关键字等于k的结点，则该结点必定是在位置mid左边的子表R[low,...,mid-1]中。因此，新的查找区间是左子表R[low,...,high]，其中high=mid-1。
若R[mid].key<k，则要查找的k必在mid的右子表R[mid+1,...,high]中，即新的查找区间是右子表R[low,...,high]，其中low=mid+1。
若R[mid].key=k，则查找成功，算法结束。

（3）下一次查找是针对新的查找区间进行，重复步骤（1）和（2）。

（4）在查找过程中，low逐步增加，而high逐步减少。如果high<low，则查找失败，算法结束。

请给出在含有12个元素的有序表{1，4，10，16，17，18，23，29，33，40，50，51}中二分查找关键字17的过程。

折半查找在查找成功时关键字的比较次数最多为⌊log₂n⌋+1次。

折半查找的时间复杂度为O(log₂n)次。

折半查找仅适用于元素有序的顺序表。

@@ 第27行： / 第27行： @@
 请给出在含有12个元素的'''<big>有序表</big>'''{1，4，10，16，17，18，23，29，33，40，50，51}中二分查找关键字17的过程。
 [[文件:二分查找.png|无|缩略图|600x600像素]]
+折半查找在查找成功时关键字的比较次数最多为⌊log<sub>2</sub>n⌋+1次。
+折半查找的时间复杂度为O(log<sub>2</sub>n)次。
+折半查找仅适用于元素有序的顺序表。