考研数据结构——C语言实现折半查找

首先定义了一个有序数组a，然后计算出数组的长度n。接着定义了一个要查找的元素x，值为79。binarySearch函数实现了二分查找算法，它接受数组、左右边界和目标值作为参数，通过不断缩小搜索范围来查找目标值。如果找到了目标值，函数返回其在数组中的索引；如果没有找到，返回-1。

在main函数中，定义了数组的左右边界，并调用binarySearch函数进行查找。根据返回的结果，使用printf函数打印出目标值在数组中的索引或者提示信息。最后，程序正常结束，返回0。

函数binarySearch实现了二分查找算法。它接收四个参数：数组arr，搜索范围的左右边界l和r，以及要查找的目标值x。函数的工作原理如下：

• 使用while循环，只要左边界l小于右边界r，就继续查找。
• 计算中间位置mid，这是通过取l和r的平均值来实现的，使用l + (r - l) / 2的写法可以防止在计算l + r时发生整数溢出。
• 如果目标值x大于中间位置的值arr[mid]，则将左边界l更新为mid + 1，缩小搜索范围到右半部分。
• 如果目标值x小于中间位置的值arr[mid]，则将右边界r更新为mid，缩小搜索范围到左半部分。
• 如果找到目标值x，则返回当前的中间位置mid作为元素的索引。
• 如果循环结束都没有找到目标值，则返回-1，表示元素不在数组中。

#include <stdio.h>int a[] = { 1, 3, 4, 4, 6, 17, 79, 81, 90 }; // 修正数组初始化
int n = sizeof(a) / sizeof(a[0]); // 计算数组元素数量
int x = 79;// 二分查找函数
int binarySearch(int arr[], int l, int r, int x) {while (l < r) {int mid = l + (r - l) / 2; // 防止溢出的写法if (x > arr[mid]) {l = mid + 1;}else if (x < arr[mid]) {r = mid;}else {return mid; // 找到元素，返回索引}}return -1; // 未找到元素，返回-1
}int main() {int left = 0, right = n - 1, result;result = binarySearch(a, left, right, x);if (result != -1) {printf("元素 %d 在数组中的索引是 %d。\n", x, result);}else {printf("数组中没有元素 %d。\n", x);}return 0;
}