应用折半查找法在一个降序序列中查找为k的元素。若查找成功,返回元素k在序列中的位置,若查找失败,返回失败信息。在序列98、86、75、64、55、48、37、22、13中查找值为22的元素并返回其位置
时间: 2023-11-14 13:05:39 浏览: 54
在一个降序序列中应用折半查找法,具体步骤如下:
1. 确定序列的左右边界,即左边界为0,右边界为序列长度减1。
2. 计算序列的中间位置mid,即mid=(left+right)/2。
3. 如果中间位置mid处的元素等于待查找元素k,则查找成功,返回mid。
4. 如果中间位置mid处的元素大于待查找元素k,则继续在左侧子序列中查找。
5. 如果中间位置mid处的元素小于待查找元素k,则继续在右侧子序列中查找。
6. 重复2-5步,直到找到待查找元素或者序列无法再分割。
在序列98、86、75、64、55、48、37、22、13中查找值为22的元素,具体步骤如下:
1. 序列为降序序列,左边界为0,右边界为序列长度减1,即left=0,right=8。
2. 计算中间位置mid,mid=(left+right)/2=4。
3. 中间位置mid处的元素为55,大于待查找元素22,因此继续在左侧子序列中查找,即right=mid-1=3。
4. 计算中间位置mid,mid=(left+right)/2=1。
5. 中间位置mid处的元素为86,大于待查找元素22,因此继续在左侧子序列中查找,即right=mid-1=0。
6. 计算中间位置mid,mid=(left+right)/2=0。
7. 中间位置mid处的元素为98,大于待查找元素22,因此继续在左侧子序列中查找,即right=mid-1=-1。
8. 此时序列无法再分割,查找失败,返回失败信息。
因此,在序列98、86、75、64、55、48、37、22、13中查找值为22的元素失败,返回失败信息。