[7/者有18个元素的有序表存放在一维数组 A119]中,第一个元素放在 A[19]中,现进行三分 查找,则查找 A[3]的比较序列的下标依次为
时间: 2023-11-14 07:04:57 浏览: 41
三分查找的过程如下:
1. 确定左右边界和中间位置。
左边界 l = 19,右边界 r = 36,中间位置 m = (l + r) / 2 = 27。
2. 比较 A[m] 和要查找的值,确定下一步查找的范围。
- 如果 A[m] > A[3],则说明要查找的值在左半边,更新右边界为 m-1。
- 如果 A[m] < A[3],则说明要查找的值在右半边,更新左边界为 m+1。
- 如果 A[m] == A[3],则说明找到了要查找的值,结束查找。
3. 重复执行步骤 1 和步骤 2,直到找到要查找的值或者左边界大于右边界。
按照上述步骤,查找 A[3] 的比较序列的下标依次为:
第一次查找:
- 左边界 l = 19,右边界 r = 36,中间位置 m = (l + r) / 2 = 27。
- 比较 A[m] = A[27] 和 A[3],发现 A[m] > A[3],因此更新右边界为 m-1,即 r = 26。
第二次查找:
- 左边界 l = 19,右边界 r = 26,中间位置 m = (l + r) / 2 = 22。
- 比较 A[m] = A[22] 和 A[3],发现 A[m] > A[3],因此更新右边界为 m-1,即 r = 21。
第三次查找:
- 左边界 l = 19,右边界 r = 21,中间位置 m = (l + r) / 2 = 20。
- 比较 A[m] = A[20] 和 A[3],发现 A[m] < A[3],因此更新左边界为 m+1,即 l = 21。
第四次查找:
- 左边界 l = 21,右边界 r = 21,中间位置 m = (l + r) / 2 = 21。
- 比较 A[m] = A[21] 和 A[3],发现 A[m] > A[3],因此更新右边界为 m-1,即 r = 20。
第五次查找:
- 左边界 l = 21,右边界 r = 20,跳出循环。
因此,查找 A[3] 的比较序列的下标依次为 27、22、20、21、20。