有序数组二分法查找c++

有序数组二分查找，也称为折半查找（Binary Search），是一种在已排序数组中快速查找特定元素的算法。其基本思想是每次将待搜索范围缩小一半，直到找到目标值或者确定范围为空。以下是C++实现二分查找的基本步骤：

template <typename T>
int binarySearch(const std::vector<T>& arr, const T& 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; // 如果找不到，返回-1表示未在数组中找到
}

在这个函数中，首先检查中间元素是否为目标值。如果不是，则根据中间元素与目标的比较结果更新搜索区间：如果中间元素小，说明目标应该在右侧；如果中间元素大，说明目标应该在左侧。这个过程会一直持续到找到目标或搜索区间为空。