C++实现折半查找

实现折半查找的过程可以分为以下几步：

步骤一：准备有序数组

折半查找需要在一个有序数组中进行查找，因此首先需要准备一个有序数组，可以使用C++中的std::sort来进行排序。

#include <iostream>
#include <algorithm>

int main() {
    int arr[] = {2, 3, 4, 5, 7, 9, 10, 12, 13, 14};
    int n = sizeof(arr) / sizeof(arr[0]);
    std::sort(arr, arr + n);  // 使用std::sort进行排序
    return 0;
}

步骤二：实现折半查找

折半查找的基本思路是：首先确定查找区间的左右边界，然后计算出中间位置，如果中间位置的值正好是查找的值，查找过程结束；如果中间位置的值比查找的值大，则在左半部分继续查找；否则在右半部分查找。

在C++中可以实现如下：

#include <iostream>

int binarySearch(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;  // 查找成功，返回下标
        else if (arr[mid] > target) right = mid - 1;  // 在左半部分查找
        else left = mid + 1;  // 在右半部分查找
    }
    return -1; // 查找失败，返回-1
}

int main() {
    int arr[] = {2, 3, 4, 5, 7, 9, 10, 12, 13, 14};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 7; // 这里查找元素7
    int res = binarySearch(arr, n, target);
    if (res == -1) std::cout << "未找到该元素\n";
    else std::cout << "该元素的下标为：" << res << "\n";
    return 0;
}

通过上面两个示例代码可以看出，原数组的大小为$N$时，折半查找的时间复杂度为$O(\log N)$，比较适合对大规模有序数据进行查找。