用c语言编写一个以有序表表示的静态顺序表的折半查找的算法程序
时间: 2024-03-18 10:41:39 浏览: 71
好的,以下是用C语言编写的以有序表表示的静态顺序表的折半查找的算法程序:
```c
#include <stdio.h>
#define MAXSIZE 100 // 定义顺序表的最大长度
typedef struct {
int data[MAXSIZE]; // 存储顺序表的数组
int length; // 存储顺序表的长度
} SqList;
/**
* 折半查找算法
* @param L 有序表
* @param key 要查找的关键字
* @return 找到则返回关键字在表中的位置,否则返回-1
*/
int BinarySearch(SqList L, int key) {
int low = 0; // 查找的下界
int high = L.length - 1; // 查找的上界
int mid; // 查找的中间值
while (low <= high) {
mid = (low + high) / 2; // 计算中间值
if (L.data[mid] == key) { // 找到了关键字
return mid; // 返回关键字在表中的位置
} else if (L.data[mid] > key) { // 关键字在左半部分
high = mid - 1; // 更新查找的上界
} else { // 关键字在右半部分
low = mid + 1; // 更新查找的下界
}
}
return -1; // 没有找到关键字
}
int main() {
SqList L = {{1, 3, 5, 7, 9}, 5}; // 定义一个有序表
int key = 5; // 要查找的关键字
int pos = BinarySearch(L, key); // 折半查找
if (pos != -1) {
printf("关键字%d在表中的位置是%d\n", key, pos);
} else {
printf("关键字%d不存在于表中\n", key);
}
return 0;
}
```
需要注意的是,这里假设顺序表中的元素已经按照从小到大的顺序排好了序。如果顺序表中的元素没有排好序,就需要先进行排序,然后再进行折半查找。
阅读全文