明白折半查找法

明白折半查找法：高效的查找算法

折半查找法（又称二分查找法）是一种高效的查找算法，用于查找一个已排序数组中的目标元素。与线性查找方法差别，折半查找每次都将搜索范围减半，从而大幅提拔查找服从。本文将具体分析折半查找的工作原理，并以查找目标值 13 为例举行内存分析。
折半查找法的根本原理

折半查找法基于如许一个假设：目标数据已经排好序。该算法通过不绝地将查找范围一分为二，渐渐缩小查找范围，从而在较短的时间内找到目标元素。具体步调如下：

• 初始化：设定一个查找范围，包罗 left 和 right，分别代表数组的起始索引和竣事索引。
  
• 盘算中央元素：每次盘算中央元素的位置，mid = left + (right - left) / 2，并与目标值举行比力。
  
• 缩小查找范围：
  
  
  
  • 假如目标值即是中央元素，返回该元素的索引。
    
  • 假如目标值小于中央元素，分析目标值在左半部门，将 right 设置为 mid - 1。
    
  • 假如目标值大于中央元素，分析目标值在右半部门，将 left 设置为 mid + 1。
    
  
  
• 循环：重复上述步调，直到找到目标元素或查找范围为空（left > right）。
  

折半查找法的时间复杂度

折半查找的时间复杂度是 (O(\log n))，此中 n 是数组的巨细。每次比力都会将查找范围减半，因此不必要遍历整个数组。相比于线性查找的 (O(n))，折半查找法的服从要高得多，尤其是在数据量较大的情况下。
源代码实现

下面是实现折半查找的 C++ 代码：

1. #include <iostream>
2. using namespace std;
4. // 折半查找函数，返回目标值的索引，找不到返回 -1
5. int binarySearch(int arr[], int size, int target) {
6.     int left = 0;
7.     int right = size - 1;
9.     while (left <= right) {
10.         int mid = left + (right - left) / 2; // 防止溢出
12.         // 检查中间元素是否是目标值
13.         if (arr[mid] == target) {
14.             return mid; // 找到目标，返回索引
15.         }
16.         // 如果目标值小于中间元素，缩小右边界
17.         else if (arr[mid] > target) {
18.             right = mid - 1;
19.         }
20.         // 如果目标值大于中间元素，缩小左边界
21.         else {
22.             left = mid + 1;
23.         }
24.     }
26.     return -1; // 目标值不在数组中
27. }
29. int main() {
30.     int arr[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19}; // 必须是有序数组
31.     int size = sizeof(arr) / sizeof(arr[0]);
32.     int target;
34.     cout << "Enter the number to search: ";
35.     cin >> target;
37.     int result = binarySearch(arr, size, target);
39.     if (result != -1) {
40.         cout << "Found " << target << " at index " << result << endl;
41.     } else {
42.         cout << target << " is not in the array." << endl;
43.     }
45.     return 0;
46. }

复制代码

以查找目标值 13 为例

假设我们有一个有序数组 arr[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19}，而且我们的目标值是 13，我们将在数组中查找目标值。
初始设置：

• 数组 arr[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19}。
  
• 目标值 target = 13。
  
• 数组巨细 size = 10，即 arr 的长度。
  
• 初始值：left = 0，right = 9。
  

1. 第一次迭代：

• left = 0, right = 9。
  
• 盘算中央索引 mid = 0 + (9 - 0) / 2 = 4，即 mid = 4。
  
• 访问 arr[mid]，即 arr[4] = 9。
  

比力 arr[mid] 与目标值 target：

• arr[mid] = 9，目标值 13 大于 9，因此目标值在右侧。
  

更新 left = mid + 1 = 4 + 1 = 5，新的查找区间是 [5, 9]。
2. 第二次迭代：

• left = 5, right = 9。
  
• 盘算中央索引 mid = 5 + (9 - 5) / 2 = 7，即 mid = 7。
  
• 访问 arr[mid]，即 arr[7] = 15。
  

比力 arr[mid] 与目标值 target：

• arr[mid] = 15，目标值 13 小于 15，因此目标值在左侧。
  

更新 right = mid - 1 = 7 - 1 = 6，新的查找区间是 [5, 6]。
3. 第三次迭代：

• left = 5, right = 6。
  
• 盘算中央索引 mid = 5 + (6 - 5) / 2 = 5，即 mid = 5。
  
• 访问 arr[mid]，即 arr[5] = 11。
  

比力 arr[mid] 与目标值 target：

• arr[mid] = 11，目标值 13 大于 11，因此目标值在右侧。
  

更新 left = mid + 1 = 5 + 1 = 6，新的查找区间是 [6, 6]。
4. 第四次迭代：

• left = 6, right = 6。
  
• 盘算中央索引 mid = 6 + (6 - 6) / 2 = 6，即 mid = 6。
  
• 访问 arr[mid]，即 arr[6] = 13。
  

比力 arr[mid] 与目标值 target：

• arr[mid] = 13，目标值 13 相当，查找乐成。
  

返回索引 6，即目标值 13 的位置。
内存分析

每次迭代，步伐都会读取 arr[mid] 并举行比力。内存访问是按需举行的，步伐仅读取当前中央位置的值，而不是遍历整个数组。每次查找范围缩小后，left 和 right 指针更新，从而镌汰了对内存的访问。通过每次将查找范围缩小一半，折半查找可以大概快速找到目标值，克制了不须要的内存读取。
总结

折半查找法通过每次将查找范围缩小一半，显着进步了查找服从。在有序数组中，我们可以大概在 (O(\log n)) 的时间复杂度内查找到目标元素。每次对数组元素的访问都是须要的，克制了线性查找中的不须要访问，使得内存访问更加高效。对于大规模数据集，折半查找法是一种抱负的查找方法。