C语言之二分查找
目录
一 简介
二分查找算法（Binary Search）在C语言中是一个用于有序数组查找特定元素的高效算法。其基本思想是通过不断将查找区间减半来逼近目标值，直到找到目标或确定目标不存在于数组中。
二 代码实现
以下是使用C语言实现二分查找算法的一个简单示例：
#include <stdio.h>
// 二分查找函数
int binarySearch(int arr[], int left, int right, int target) {
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; // 在左半部分（包括中间点左侧）进行查找
}
}
// 若未找到目标值，则返回-1表示目标值不在数组中
return -1;
}
int main() {
int sortedArray[] = {1, 3, 5, 7, 9, 11, 13, 15};
int n = sizeof(sortedArray) / sizeof(sortedArray[0]);
int target = 7;
int result = binarySearch(sortedArray, 0, n - 1, target);
if (result != -1) {
printf("Element %d is present at index %d.\n", target, result);
} else {
printf("Element %d is not found in the array.\n", target);
}
return 0;
}在这段代码中：
binarySearch函数接受一个已排序的整数数组、左边界索引、右边界索引以及要查找的目标值。- 它首先计算数组中间位置的索引，并与目标值比较。
- 如果目标值等于中间元素，那么就找到了目标并返回其索引。
- 如果目标值小于中间元素，说明目标值应该位于中间元素的左边，因此更新右边界为“中间索引 - 1”。
- 否则，目标值应该位于中间元素的右边，所以更新左边界为“中间索引 + 1”。
- 这个过程会一直重复，直到找到目标值或者左右边界交叉，此时表明目标值不在数组中。
三 时空复杂度
二分查找算法（Binary Search）是一种在有序数组中查找特定元素的高效算法。其时空复杂度如下：
A.时间复杂度（Time Complexity）：
- 平均情况和最好情况下，二分查找的时间复杂度都是 O(log n)，其中 n 为数组中的元素个数。这是因为每次迭代都将搜索区间减半，直到找到目标值或搜索区间为空。
最坏情况下，如果要查找的元素不在数组中，那么同样需要进行 log n 次比较才能确定这一点，所以即使在最坏情况下，时间复杂度仍然是 O(log n)。
B.空间复杂度（Space Complexity）：
- 二分查找的空间复杂度是 O(1) 或常数空间复杂度。这是因为算法在执行过程中仅使用了几个固定大小的变量，如存储中间索引、左边界和右边界的变量，并未依赖于输入数据规模大小的数据结构。无论输入数组多大，辅助空间的需求保持不变。
C.总结
总结来说，二分查找算法具有非常优秀的效率，在处理大规模有序数据时尤为适用，它能够在相对较短的时间内完成查找任务，且占用的空间资源极小。