目录
前提条件
核心思想
方式1——递归实现（分治算法）
方式2——迭代实现
-
前提条件
- 数据结构：必须采用顺序存储结构，例如数组，这样才能通过下标随机访问元素。
- 元素有序性：数组中的元素必须是有序的，即按照升序或降序排列。如果数组无序，二分查找将无法正确工作。
-
核心思想
- 利用数组的有序性，通过不断将查找区间缩小为原来的一半，来快速定位目标元素。每次比较都能排除掉一半的查找范围，从而大大提高查找效率。
-
方式1——递归实现（分治算法）
#include <stdio.h>// 二分查找函数，返回目标值在数组中的索引，不存在则返回 -1
int binarySearch(int arr[], int left, int right, int target) {if (left > right) {return -1; // 未找到目标值}int mid = left + (right - left) / 2; // 计算中间索引，防止溢出if (arr[mid] == target) {return mid; // 找到目标值，返回索引} else if (arr[mid] > target) {return binarySearch(arr, left, mid - 1, target); // 在左半部分继续查找} else {return binarySearch(arr, mid + 1, right, target); // 在右半部分继续查找}
}int main() {int arr[] = {1, 3, 5, 7, 9, 11, 13, 15};int len = sizeof(arr) / sizeof(arr[0]);int target = 9;int result = binarySearch(arr, 0, len - 1, target);if (result != -1) {printf("目标值 %d 在数组中的索引是 %d\n", target, result);} else {printf("目标值 %d 不在数组中\n", target);}return 0;
}-
方式2——迭代实现
#include<stdio.h>// 二分查找法 —— 在一个有序数组里查找特定元素的位置
int binarySearch(int arr[], int low, int high, int value) {while (low <= high) {int mid = (low + high) / 2;if (arr[mid] < value){low = mid + 1;}else if (arr[mid] > value) {high = mid - 1;}else{return mid;}}return -1;//代表在该数组中没有找到该元素
}int main() {//测试二分查找法——查找11这个值int arr2[] = { 3,4,6,11,19,22,46 };int len2 = sizeof(arr2) / sizeof(arr2[0]);int index = binarySearch(arr2, 0, len2 - 1, 11);if (index != -1){printf("11在数组中的第%d个位置!\n", index + 1);//4}else {printf("11不存在数组arr2内!\n");}return 0;
}两种实现方式的区别
实现方式
- 递归（分治算法）：分治算法实现的二分查找通过递归调用自身来不断缩小查找范围。每次递归时，根据中间元素与目标值的比较结果，决定是在左半部分还是右半部分继续递归查找。
- 迭代：迭代方式使用
while循环来不断更新查找范围的左右边界，直到找到目标值或者确定目标值不存在。
代码结构
- 递归：递归实现的代码结构更加简洁和直观，因为它直接体现了分治的思想。递归函数会不断调用自身，直到满足终止条件。
- 迭代：迭代实现使用循环结构，代码相对复杂一些，需要手动管理循环变量和边界条件。
终止条件
- 递归：递归的终止条件通常是查找范围为空（
left > right）或者找到目标值。当满足终止条件时，递归函数会返回结果。 - 迭代：迭代的终止条件是查找范围的左边界大于等于右边界（
low >= high），此时循环结束，根据情况返回结果。
内存使用
- 递归：递归实现会在调用栈上创建多个函数调用帧，每个调用帧都会占用一定的内存空间。如果数组规模较大，递归深度可能会很深，导致栈溢出的风险。
- 迭代：迭代实现只使用了常数级的额外空间，不会像递归那样占用大量的栈空间，因此在内存使用上更加高效。
性能
- 时间复杂度：两种实现方式的时间复杂度都是 (O(log n))，因为每次查找都会将查找范围缩小一半。
- 空间复杂度：递归实现的空间复杂度是 (O(log n))，主要是递归调用栈的空间开销；迭代实现的空间复杂度是 (O(1))，只使用了常数级的额外空间。