假如静态表查找表{2,5,7,17,23,25,31,35,42,76,88},请写出采用折半查找算法查找关键字为17的过程
时间: 2024-06-07 20:08:37 浏览: 46
折半查找算法的过程如下:
1. 确定查找区间的左右端点,初始时左端点为0,右端点为数组长度减1。
2. 计算中间位置mid,即 mid = (left + right) / 2。
3. 比较中间位置的值与目标值的大小关系。若相等,则查找成功,返回该位置;若中间位置的值大于目标值,则在左半部分继续查找;否则在右半部分继续查找。
4. 若左端点大于右端点,则查找失败,返回-1。
按照上述步骤,查找关键字为17的过程如下:
1. 初始时,左端点为0,右端点为10(数组长度减1),mid = (0 + 10) / 2 = 5。
2. 数组中下标为5的元素为25,大于目标值17,说明目标值在左半部分,将右端点更新为mid-1=4,此时左端点为0,右端点为4。
3. 计算mid = (0 + 4) / 2 = 2,数组中下标为2的元素为7,小于目标值17,说明目标值在右半部分,将左端点更新为mid+1=3,此时左端点为3,右端点为4。
4. 计算mid = (3 + 4) / 2 = 3,数组中下标为3的元素为17,查找成功,返回该位置。
因此,关键字17在静态表中的下标为3。
阅读全文