用C语言,编程实现有序顺序表的折半查找(升序和降序)
时间: 2024-03-11 13:51:06 浏览: 75
好的,下面是实现有序顺序表的折半查找的代码:
```c
#include <stdio.h>
// 有序顺序表的折半查找(升序)
int binary_search_asc(int *arr, int len, int key)
{
int left = 0, right = len - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == key) {
return mid;
} else if (arr[mid] < key) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
// 有序顺序表的折半查找(降序)
int binary_search_desc(int *arr, int len, int key)
{
int left = 0, right = len - 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(void)
{
int arr[] = {1, 3, 5, 7, 9, 11, 13};
int len = sizeof(arr) / sizeof(arr[0]);
int index_asc = binary_search_asc(arr, len, 7);
if (index_asc != -1) {
printf("在升序数组中找到了 7,下标为 %d\n", index_asc);
} else {
printf("在升序数组中没有找到 7\n");
}
int index_desc = binary_search_desc(arr, len, 7);
if (index_desc != -1) {
printf("在降序数组中找到了 7,下标为 %d\n", index_desc);
} else {
printf("在降序数组中没有找到 7\n");
}
return 0;
}
```
以上代码中,`binary_search_asc` 函数实现了在升序数组中进行折半查找,`binary_search_desc` 函数实现了在降序数组中进行折半查找。两个函数的实现基本相同,只是在比较元素大小时的判断条件不同。函数返回值为查找到的元素下标,如果没有找到则返回 -1。
阅读全文