若有18个元素的有序表存放在一维数组 A[19]中,第一个元素放在 A[1]中,现进行二分查找,则查找 A[3]的比较序列的下标依次为
时间: 2023-11-13 09:02:24 浏览: 96
二分查找的基本思想是:在有序表中,先取中间位置的记录进行比较,如果要查找的关键字小于中间位置记录的关键字,则在中间位置的左半区继续查找;如果要查找的关键字大于中间位置记录的关键字,则在中间位置的右半区继续查找,直到查找成功或失败为止。
对于有序表 A[19],进行二分查找,首先需要确定查找区间的左右边界,即 low 和 high 的值,由于 A[1] 到 A[18] 共有 18 个元素,因此可取 low=1,high=18。接下来,需要通过比较中间元素 A[mid] 和查找关键字的大小来缩小查找范围,其中 mid=(low+high)/2。
第一次比较时,mid=9,A[mid]=A[9]=?,因为题目没有给出具体的数据,因此无法确定 A[9] 的值,只能假设 A[9] 的值为 x,若 x<A[3],则继续在 A[1] 到 A[8] 的区间内查找,即 high=mid-1=8;若 x>A[3],则继续在 A[10] 到 A[18] 的区间内查找,即 low=mid+1=10;若 x=A[3],则查找成功,返回 mid=9。
第二次比较时,mid=4,A[mid]=A[4]=?,若 A[4]<A[3],则继续在 A[5] 到 A[8] 的区间内查找,即 high=mid-1=3;若 A[4]>A[3],则继续在 A[1] 到 A[3] 的区间内查找,即 low=1,high=mid-1=3,此时 mid=(1+3)/2=2,A[mid]=A[2]=?,若 A[2]<A[3],则继续在 A[3] 到 A[3] 的区间内查找,即 high=low=3;若 A[2]>A[3],则继续在 A[1] 到 A[1] 的区间内查找,即 high=low=1;若 A[2]=A[3],则查找成功,返回 mid=2。
因此,查找 A[3] 的比较序列的下标依次为 9、2。
相关推荐
![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_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)