C++ 折半查找算法实现：在有序数组中快速查找元素

折半查找（也称为二分查找）是一种高效的查找算法，适用于有序数组。它通过不断缩小查找范围，快速定位目标元素。

以下是一个简单的折半查找算法的 C++ 实现代码：

#include <iostream>
using namespace std;

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;
    }
    return -1;
}

int main() {
    int arr[] = { 1, 3, 5, 7, 9, 11 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 5;
    int index = binarySearch(arr, 0, n - 1, target);
    if (index == -1)
        cout << 'Element not found in array';
    else
        cout << 'Element found at index ' << index;
    return 0;
}

代码解析：

binarySearch 函数
- 该函数接受四个参数：
  - arr：待查找的数组
  - left：查找范围的左边界
  - right：查找范围的右边界
  - target：要查找的目标元素
- 使用 while 循环不断缩小查找范围，直到找到目标元素或查找范围为空为止。
- 在每次循环迭代中：
  - 计算中间元素的索引 mid。
  - 将目标元素与中间元素进行比较：
    - 若 arr[mid] == target，则找到目标元素，返回其索引 mid。
    - 若 arr[mid] < target，则目标元素在右侧，更新 left 为 mid + 1。
    - 若 arr[mid] > target，则目标元素在左侧，更新 right 为 mid - 1。
- 若未找到目标元素，返回 -1。
主函数
- 定义一个有序数组 arr。
- 调用 binarySearch 函数进行查找。
- 根据返回值判断目标元素是否找到，并输出相应信息。

折半查找的优点：

效率高，时间复杂度为 O(log n)。
代码简洁易懂。

适用场景：

在有序数组中查找元素。
需要快速定位目标元素。

注意：

折半查找算法要求数组必须有序。
若数组中存在重复元素，则可能返回任意一个重复元素的索引。

希望本文能够帮助你理解和使用 C++ 实现的折半查找算法。