用折半查找在有序序列 { 6 , 15 , 20 , 32 , 56 , 70 , 83 }中查找值为15的记录的过程中,首先让15与 比较。
时间: 2024-01-18 18:04:08 浏览: 17
用折半查找在有序序列 { 6 , 15 , 20 , 32 , 56 , 70 , 83 }中查找值为15的记录的过程中,首先让15与中间位置的元素 32 进行比较。由于 15 小于 32,所以在左侧继续查找。
接下来,将左侧的序列 { 6 , 15 , 20 } 再次进行折半查找,让 15 与中间位置的元素 15 进行比较。由于 15 等于 15,所以找到了要查找的元素。
相关问题
使用折半查找法在有序序列(升序或降序)中,按值查找记录。若查找成功,返回记录在序列中的位置(位序,从1开始),若查找失败,返回0。
折半查找法又称二分查找法,是一种高效的查找算法。它的基本思想是:对于有序序列,从中间位置开始查找,如果中间位置的值大于要查找的值,则在左半部分继续查找,否则在右半部分查找。每次查找都可以将待查找的区间缩小一半,直到查找成功或者区间缩小为0为止。
以下是使用折半查找法在有序序列中查找记录的示例代码(假设序列是升序排列):
```
int binarySearch(int array[], int n, int key) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (array[mid] == key) {
return mid + 1;
} else if (array[mid] < key) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return 0;
}
```
其中,`array`是有序序列,`n`是序列的长度,`key`是要查找的值。`left`和`right`分别表示当前待查找区间的左右边界。每次循环计算出中间位置`mid`,如果中间位置的值等于要查找的值,则返回`mid+1`(因为题目要求从1开始计数)。如果中间位置的值小于要查找的值,则在右半部分继续查找,否则在左半部分查找。最终如果查找失败(即待查找区间缩小为0),则返回0。
设有有序数字序列a:{1, 2, 5, 7, 9, 10, 15, 20,28}, 写出用折半查找法查找15的过程
好的,我来为您演示一下用折半查找法查找15的过程:
1. 首先确定查找范围,因为序列是有序的,所以我们可以取最左边的元素下标left为0,最右边的元素下标right为8,即a序列的长度减1。
2. 计算中间位置mid,mid的计算公式为mid = (left + right) / 2,即mid = 4。
3. 比较a[mid]与要查找的元素15,因为a[mid] = 9 < 15,所以15应该在右半部分序列中。
4. 更新查找范围,因为15在右半部分序列中,所以我们可以把左边界left更新为mid+1,即left = 5。
5. 再次计算中间位置mid,mid的计算公式为mid = (left + right) / 2,即mid = 6。
6. 比较a[mid]与要查找的元素15,因为a[mid] = 15,所以查找成功,返回元素15的下标6。
因此,使用折半查找法可以在a序列中找到元素15,其下标为6。
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.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)