关于列表的问题

Chihirotlmt

设有序单链表的关键字序列为{1,4,6,11,19,35,52,54,57,71,78,86,92,96}，当查找关键字为21的结点时，经( )次比较后查找失败？

isdkz

这里可以使用二分查找算法来查找关键字为21的结点。

二分查找算法是针对有序序列进行查找的一种高效算法，它的基本思路是将查找区间不断缩小一半，直到找到目标元素或者查找区间为空为止。下面是使用二分查找算法来查找关键字为21的结点的过程：

1、初始化左右边界：left=0，right=len(list)-1=13。

2、循环执行以下步骤，直到left>right为止：

a. 计算中间位置mid=(left+right)//2=6。

b. 将要查找的值21与中间位置的值list[mid]比较，如果相等则查找成功，返回结点位置mid；如果要查找的值小于中间位置的值，则将右边界right更新为mid-1；如果要查找的值大于中间位置的值，则将左边界left更新为mid+1。

c. 重复步骤2。

3、如果查找区间为空仍未找到要查找的值，则查找失败，返回-1。

根据以上算法，当查找关键字为21的结点时，经3次比较后查找失败。

详细的查找过程如下：

第一轮：left=0，right=13，mid=6，list[mid]=52，21<52，所以right=mid-1=5。

第二轮：left=0，right=5，mid=2，list[mid]=6，21>6，所以left=mid+1=3。

第三轮：left=3，right=5，mid=4，list[mid]=19，21>19，所以left=mid+1=5。

第四轮：left=5，right=5，mid=5，list[mid]=35，21<35，所以right=mid-1=4。

第五轮：left=5，right=4，循环结束，查找失败。

sfqxx

此单链表已经按照关键字从小到大的顺序排好，因此可以使用二分查找算法进行查找，每次比较后可以将查找范围缩小一半，直到查找成功或者失败。

具体实现步骤如下：

1. 设定搜索区间的左右端点left和right，初始时left=0，right=13，表示整个有序序列为搜索区间。
2. 计算中间位置mid=(left+right)/2，并取出该位置的元素与待查找元素进行比较。
3. 如果mid位置的元素等于待查找元素，则查找成功，返回mid值。
4. 如果mid位置的元素大于待查找元素，则在左半部分继续查找。更新right=mid-1，重复第2步。
5. 如果mid位置的元素小于待查找元素，则在右半部分继续查找。更新left=mid+1，重复第2步。
6. 如果left>right，则表示搜索区间内没有待查找元素，查找失败，返回-1。

按照上述步骤进行查找，可以得到以下过程：

left	right	mid	比较次数
----	-----	----	--------
0	13	6	1
7	13	10	2
11	13	12	3
13	13	-	4

最终查找失败，比较次数为4次。
有用请设置最佳答案

陶远航

有序单链表的查找通常采用顺序查找的方法，即从表头开始，依次比较每个结点的关键字与给定值是否相等，直到找到或遍历完整个链表为止。因此，当查找关键字为21的结点时，需要从第一个结点开始，依次与1,4,6,11,19,35进行比较，共6次比较后查找失败。