Page 126 - 高中 信息技术 选择性必修1 数据与数据结构

第五章 数据结构的应用

二分查找过程分析：假设一维数组a中有10个元素：1，2，6，8，12，13，36，45，
49，85，在其中查找k=45的过程如下（用“[ ]”表示low和high，即当前查找范围的下界和
上界，mid指示查找范围的中间位置）：

下标 0 1 2 3 4 5 6 7 8 9
第一次查找：元素［1 2 6 8 12 13 36 45 49 85］
↑
mid
mid=(0+9)/2=4，取a[4]元素12，因为12<45，所以low=mid+1=5。
广东教育出版社
第二次查找：元素 1 2 6 8 12［13 36 45 49 85］
↑
mid
mid=(5+9)/2=7，a[7]元素为45，查找成功，返回mid=7。

在其中查找k=48的过程如下：

下标 0 1 2 3 4 5 6 7 8 9
第一次查找：元素［1 2 6 8 12 13 36 45 49 85］
↑
mid
mid=(0+9)/2=4，取a[4]元素12，因为12<48，所以low=mid+1=5。
第二次查找：元素 1 2 6 8 12［13 36 45 49 85］
↑
mid

mid=(5+9)/2=7，取a[7]元素45，因为45<48，所以low=mid+1=8。
第三次查找：元素 1 2 6 8 12 13 36 45［49 85］
↑
mid
mid=(8+9)/2=8，取a[8]元素49，因为49>48，所以high=mid-1=7。
第四次查找：元素 1 2 6 8 12 13 36 45］［49 85

↑↑
high low

此时，high<low，循环结束，说明查找失败，返回-1。

118 118

21X2204.indd 118 2019/9/26 13:53:39