关于列表的问题
设有序单链表的关键字序列为{1,4,6,11,19,35,52,54,57,71,78,86,92,96}，当查找关键字为21的结点时，经( )次比较后查找失败？本帖最后由 isdkz 于 2023-4-9 16:26 编辑
这里可以使用二分查找算法来查找关键字为21的结点。
二分查找算法是针对有序序列进行查找的一种高效算法，它的基本思路是将查找区间不断缩小一半，直到找到目标元素或者查找区间为空为止。下面是使用二分查找算法来查找关键字为21的结点的过程：
1、初始化左右边界：left=0，right=len(list)-1=13。
2、循环执行以下步骤，直到left>right为止：
a. 计算中间位置mid=(left+right)//2=6。
b. 将要查找的值21与中间位置的值list比较，如果相等则查找成功，返回结点位置mid；如果要查找的值小于中间位置的值，则将右边界right更新为mid-1；如果要查找的值大于中间位置的值，则将左边界left更新为mid+1。
c. 重复步骤2。
3、如果查找区间为空仍未找到要查找的值，则查找失败，返回-1。
根据以上算法，当查找关键字为21的结点时，经3次比较后查找失败。
详细的查找过程如下：
第一轮：left=0，right=13，mid=6，list=52，21<52，所以right=mid-1=5。
第二轮：left=0，right=5，mid=2，list=6，21>6，所以left=mid+1=3。
第三轮：left=3，right=5，mid=4，list=19，21>19，所以left=mid+1=5。
第四轮：left=5，right=5，mid=5，list=35，21<35，所以right=mid-1=4。
第五轮：left=5，right=4，循环结束，查找失败。 本帖最后由 sfqxx 于 2023-4-9 16:32 编辑
此单链表已经按照关键字从小到大的顺序排好，因此可以使用二分查找算法进行查找，每次比较后可以将查找范围缩小一半，直到查找成功或者失败。
具体实现步骤如下：
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次。
有用请设置最佳答案 本帖最后由 陶远航 于 2023-4-9 17:40 编辑
有序单链表的查找通常采用顺序查找的方法，即从表头开始，依次比较每个结点的关键字与给定值是否相等，直到找到或遍历完整个链表为止。因此，当查找关键字为21的结点时，需要从第一个结点开始，依次与1,4,6,11,19,35进行比较，共6次比较后查找失败。
页:
[1]