简单c语言代码折半查找【问题描述】 从键盘输入若干个关键字序列(不超过999个关键字),以0作为输入结束。编写代码实现折半查找关键字,查找成功输出关键字的位置,否则输出not found。 【输入形式】第一行输入若干个关键字
时间: 2024-03-11 10:44:25 浏览: 78
序列,以0作为输入结束。接下来一行输入要查找的关键字。 【输出形式】若查找成功,输出关键字在序列中的位置;否则输出not found。 【样例输入】
1 2 3 4 5 6 7 8 9 10 0
6
【样例输出】
5
【样例说明】
输入若干个关键字序列为1 2 3 4 5 6 7 8 9 10,查找6的位置为5。
【解题思路】
使用折半查找的思路,先将输入的关键字序列排序,然后在排好序的序列中进行折半查找。
相关问题
简单c语言代码顺序查找【问题描述】 从键盘输入若干个关键字序列(不超过999个关键字),以0作为输入结束。编写代码实现折半查找关键字,查找成功输出关键字的位置,否则输出not found。
以下是简单的C语言代码,实现了顺序查找:
```c
#include <stdio.h>
#define MAX_SIZE 1000
int main()
{
int i, n, key;
int a[MAX_SIZE];
printf("请输入关键字序列,以0作为输入结束:\n");
// 读入关键字序列
i = 0;
do {
scanf("%d", &a[i]);
i++;
} while (a[i-1] != 0 && i < MAX_SIZE);
n = i - 1;
// 读入待查找的关键字
printf("请输入待查找的关键字:\n");
scanf("%d", &key);
// 顺序查找
for (i = 0; i < n; i++) {
if (a[i] == key) {
printf("关键字 %d 的位置为 %d\n", key, i+1);
return 0;
}
}
printf("not found\n");
return 0;
}
```
代码中先读入关键字序列,以0作为输入结束,并记录序列中关键字的个数n。然后读入待查找的关键字key,并在关键字序列中顺序查找key,找到则输出位置,否则输出not found。
编写算法,实现对n个关键字的序列进行调整,使得序列中奇数排在偶数的前面,要求算法需要一个辅助空间,时间复杂度为0(n),使用折半查找法查找输入的某个关键字是否存在的c语言代码
以下是给出的C语言代码实现:
1. 实现奇偶数调整:
```c
void adjust(int arr[], int n) {
int i = 0, j = n - 1;
while (i < j) {
while (i < j && arr[i] % 2 != 0) i++;
while (i < j && arr[j] % 2 == 0) j--;
if (i < j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
}
```
2. 折半查找法查找某个关键字:
```c
int binary_search(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;
}
```
阅读全文