使用折半查找法在有序序列(升序或降序)中,按值查找记录。若查找成功,返回记录在序列中的位置(位序,从1开始),若查找失败,返回0。
时间: 2024-05-16 07:16:42 浏览: 89
采用折半查找和顺序查找来查找某个数
折半查找法又称二分查找法,是一种高效的查找算法。它的基本思想是:对于有序序列,从中间位置开始查找,如果中间位置的值大于要查找的值,则在左半部分继续查找,否则在右半部分查找。每次查找都可以将待查找的区间缩小一半,直到查找成功或者区间缩小为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。
阅读全文