close

C++ 中的二分查找 (Binary Search) 算法- 解释、示例和代码

二分搜索算法是在排序列表中搜索特定元素的更有效方法。 与顺序检查元素的线性搜索不同，二分搜索将列表分成两半，并将目标元素与中间元素进行比较。 重复此过程，直到找到目标元素或搜索范围变空。

怎么运行的

  1. 从整个排序列表开始。
  2. 查找当前搜索范围的中间元素。
  3. 将中间元素与目标值进行比较。
  4. 如果中间元素等于目标值，则查找成功。
  5. 如果中间元素大于目标，则在范围的左半部分搜索。
  6. 如果中间元素小于目标，则在范围的右半部分搜索。
  7. 重复步骤2-6，直到找到目标元素或搜索范围变空。

例子

让我们考虑一个排序的整数列表，并希望使用二分查找找到数字 34。

排序列表：{12, 23, 34, 45, 56, 67, 89, 90}

  1. 从整个列表开始。
  2. 中间元素：56（位置 4）。 与34相比。
  3. 56 大于 34。在左半部分搜索。
  4. 新的中间元素：23（位置 1）。 与34相比。
  5. 23 比 34 小。在右半部分搜索。
  6. 新的中间元素：45（位置 3）。 与34相比。
  7. 45 大于 34。在左半部分搜索。
  8. 新的中间元素：34（位置 2）。 目标已找到。

C++ 示例代码 

#include <iostream>  
#include <vector>  
  
int binarySearch(const std::vector<int>& arr, int target) {  
    int left = 0;  
    int right = arr.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() {  
    std::vector<int> numbers = {12, 23, 34, 45, 56, 67, 89, 90};  
    int target = 34;  
  
    int result = binarySearch(numbers, target);  
  
    if(result != -1) {  
        std::cout << "Element " << target << " found at position " << result << std::endl;  
    } else {  
        std::cout << "Element " << target << " not found in the array" << std::endl;  
    }  
  
    return 0;  
}

在给定的示例中，该 binarySearch 函数用于在整数排序列表中查找数字 34。 结果将是列表中 34 的位置（位置从 0 开始），如果未找到该数字，则结果为 -1。