在计算机科学中，折半查找（Binary Search）是一种高效的数据查找算法，尤其适用于已经排序好的数据集合。它通过将目标值与中间元素进行比较，不断缩小搜索范围，从而快速定位目标值的位置。本文将介绍如何使用C语言实现这一经典算法，并提供一个完整的代码示例。
首先，我们需要明确折半查找的基本步骤：
1. 确定数组的起始索引和结束索引。
2. 计算中间索引，获取中间元素。
3. 比较中间元素与目标值：
- 如果相等，则找到目标值，返回其索引；
- 如果中间元素大于目标值，则在左半部分继续查找；
- 如果中间元素小于目标值，则在右半部分继续查找。
4. 重复上述过程，直到找到目标值或搜索范围为空。
下面是一个简单的C语言实现：
```c
include
int binarySearch(int arr[], int size, int target) {
int left = 0;
int right = size - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // 防止溢出
if (arr[mid] == target) {
return mid; // 找到目标值，返回索引
} else if (arr[mid] < target) {
left = mid + 1; // 在右半部分查找
} else {
right = mid - 1; // 在左半部分查找
}
}
return -1; // 未找到目标值
}
int main() {
int arr[] = {1, 3, 5, 7, 9, 11, 13, 15};
int size = sizeof(arr) / sizeof(arr[0]);
int target = 7;
int result = binarySearch(arr, size, target);
if (result != -1) {
printf("Element found at index %d\n", result);
} else {
printf("Element not found in the array.\n");
}
return 0;
}
```
代码解析：
- `binarySearch` 函数接收三个参数：一个整数数组 `arr`，数组大小 `size` 和目标值 `target`。
- 使用两个变量 `left` 和 `right` 来表示当前搜索范围的起始和结束索引。
- 循环条件 `while (left <= right)` 确保搜索范围有效。
- 通过 `(left + (right - left) / 2)` 计算中间索引，避免了可能的溢出问题。
- 根据中间元素与目标值的关系调整搜索范围。
- 如果找到目标值，返回其索引；否则返回 `-1` 表示未找到。
