若有18个元素的有序表存放在一维数组A[19]中,第一个元素放在A[1]中,现进行二分查找,则查找A[3]的比较序列的下标依次为( )。
时间: 2023-12-14 10:02:03 浏览: 71
二分查找的过程是每次将待查找区间缩小一半,因此比较序列的下标应该是单调不降的。
假设当前待查找区间左右端点分别为 $L$ 和 $R$,则中间位置为 $mid=\lfloor (L+R)/2 \rfloor$。
- 如果 $A[mid] = A[3]$,那么查找成功,比较序列的下标为 $mid$。
- 如果 $A[mid] < A[3]$,那么 $A[1\sim mid]$ 都比 $A[3]$ 小,因此待查找区间应该变为 $[mid+1, R]$。
- 如果 $A[mid] > A[3]$,那么 $A[mid \sim 19]$ 都比 $A[3]$ 大,因此待查找区间应该变为 $[L, mid-1]$。
根据上述过程,查找 $A[3]$ 的比较序列的下标依次为:
- 第一次查找时,待查找区间为 $[1, 19]$,中间位置为 $mid=9$,$A[9] > A[3]$,所以待查找区间变为 $[1, 8]$。
- 第二次查找时,待查找区间为 $[1, 8]$,中间位置为 $mid=4$,$A[4] < A[3]$,所以待查找区间变为 $[5, 8]$。
- 第三次查找时,待查找区间为 $[5, 8]$,中间位置为 $mid=6$,$A[6] < A[3]$,所以待查找区间变为 $[7, 8]$。
- 第四次查找时,待查找区间为 $[7, 8]$,中间位置为 $mid=7$,$A[7] > A[3]$,所以待查找区间变为 $[7, 6]$。
- 最后查找时,待查找区间为 $[7, 6]$,查找失败。
因此,查找 $A[3]$ 的比较序列的下标依次为 $9, 4, 6, 7$。
相关推荐
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)