8.对一组有序的数据{1,3,7,22,55,66,88,90,100,150,120}，采用二分法查找算法，查找给定的一个数是否存在，若查找成功给出所在的位置并输出查找次数，否则输出“不存在”

### 二分法查找算法的实现方法以及如何在有序数组中查找给定数字的位置和计算查找次数 #### C++ 实现 下面提供了一种基于迭代方式的二分查找实现，同时记录了查找过程中所执行的比较次数。 ```cpp #include <iostream> using namespace std; // 函数声明 int binarySearch(int arr[], int size, int target, int& comparisons); int main() { // 初始化一个已排序的数组 int sortedArray[] = {1, 3, 5, 7, 9, 11, 13, 15}; int size = sizeof(sortedArray) / sizeof(sortedArray[0]); int targetValue; cout << "请输入要查找的目标值: "; cin >> targetValue; int comparisonCount = 0; // 记录比较次数 int resultIndex = binarySearch(sortedArray, size, targetValue, comparisonCount); if (resultIndex != -1) { cout << "目标值 " << targetValue << " 的索引为：" << resultIndex << endl; } else { cout << "未找到目标值 " << targetValue << " 在数组中的位置。" << endl; } cout << "总共进行了 " << comparisonCount << " 次比较。" << endl; return 0; } // 迭代版二分查找函数 int binarySearch(int arr[], int size, int target, int& comparisons) { int low = 0; int high = size - 1; while (low <= high) { ++comparisons; // 每次进入循环即增加一次比较次数 int mid = low + (high - low) / 2; // 防止溢出的方式计算中间索引 if (arr[mid] == target) { // 找到目标值 return mid; } else if (arr[mid] < target) { // 目标值在右侧子数组 low = mid + 1; } else { // 目标值在左侧子数组 high = mid - 1; } } return -1; // 未找到目标值 } ``` 此代码实现了基本的二分查找，并且引入了一个额外参数 `comparisonCount` 来跟踪每次比较的操作次数[^1]。 --- #### Python 实现 下面是使用递归方式进行二分查找的一个例子，同样包含了查找次数的统计功能。 ```python def binary_search_recursive(arr, low, high, target, comparisons=0): """ 使用递归实现二分查找并统计比较次数。 参数: arr -- 已排序的数组 low -- 当前搜索区间的起始索引 high -- 当前搜索区间的结束索引 target -- 要查找的目标值 comparisons -- 当前已经完成的比较次数 返回: tuple -- 包含目标值所在索引和总的比较次数 (-1 表示未找到) """ if low > high: return (-1, comparisons) comparisons += 1 # 每次递归调用视为一次比较 mid = low + (high - low) // 2 if arr[mid] == target: return (mid, comparisons) elif arr[mid] < target: return binary_search_recursive(arr, mid + 1, high, target, comparisons) else: return binary_search_recursive(arr, low, mid - 1, target, comparisons) if __name__ == "__main__": # 示例输入 sorted_array = [1, 3, 5, 7, 9, 11, 13, 15] target_value = int(input("请输入要查找的目标值: ")) index, total_comparisons = binary_search_recursive( sorted_array, 0, len(sorted_array) - 1, target_value ) if index != -1: print(f"目标值 {target_value} 的索引为：{index}") else: print(f"未找到目标值 {target_value} 在数组中的位置。") print(f"总共进行了 {total_comparisons} 次比较。") ``` 在这个版本里，通过递归来逐步缩小搜索范围直至找到目标或确定其不存在于数组之中[^2]。 --- #### 关键点解释 - **时间复杂度**: 不论是迭代还是递归的形式，二分查找的时间复杂度均为 \(O(\log n)\)，其中 \(n\) 是数组长度[^4]。 - **空间复杂度**: - 对于迭代版本的空间复杂度为 \(O(1)\)，因为它只用了固定的几个变量来辅助运算； - 而递归版本由于涉及栈帧开销，所以其空间复杂度取决于最大递归深度，通常也是 \(O(\log n)\)[^1]^。 - **适用场景**: 只能应用于严格单调递增或者递减排列的数据集合之上[^3]. --- ###