在 $n$ 个整数构成的有序序列中,找到关键字 $key$ 在序列中出现的位置。当 $key$ 在序列中不出现时,输出 No。 为了提高查找效率,利用待查找序列有序的特征,程序使用“二分查找”的算法。二分查找的做法是:首先,将表中间位置记录的关键字与查找关键字 $key$ 比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。 在提示部分已经给出部分代码,将程序补充完整,并提交规定的部分。 输入 先输入 $n$ 个表示待查找的序列中的元素个数。 再输入 $n$ 个整数作为待查找序列,这些整数按从小到大的顺序排列。 最后输入要查找的数 $key$。 输出 输出 $key$ 在序列出现的位置,若不出现,输出 No。用c语言实现
时间: 2024-02-13 10:07:12 浏览: 21
以下是代码实现:
```c
#include <stdio.h>
int binarySearch(int arr[], int n, int key) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == key) {
return mid;
} else if (arr[mid] > key) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
int main() {
int n, key;
scanf("%d", &n);
int arr[n];
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
scanf("%d", &key);
int index = binarySearch(arr, n, key);
if (index >= 0) {
printf("%d\n", index);
} else {
printf("No\n");
}
return 0;
}
```
这里使用了二分查找的算法,时间复杂度为 $O(\log n)$。首先设定左右两个指针,分别指向数组的最左端和最右端,然后计算出中间位置的下标,比较中间位置的元素与要查找的元素的大小关系,如果相等则返回中间位置的下标,如果中间位置的元素大于要查找的元素,则在左半部分继续查找,否则在右半部分继续查找,直到找到要查找的元素或者找不到为止。如果找不到则返回 -1。