C++实现折半查找法

在C++中，折半查找（也称为二分查找）是一种非常高效的在有序数组中查找特定元素的搜索算法。以下是基本的折半查找法的C++实现：

// 定义一个辅助函数用于二分查找
template <typename T>
size_t binarySearch(const std::vector<T>& arr, const T& target) {
    size_t left = 0;
    size_t right = arr.size() - 1;

    // 当左指针小于等于右指针时继续循环
    while (left <= right) {
        // 计算中间索引
        size_t mid = left + (right - left) / 2;

        // 检查中间元素是否为目标值
        if (arr[mid] == target) {
            // 找到目标，返回其索引
            return mid;
        }
        // 如果中间元素大于目标，缩小搜索范围到左半部分
        else if (arr[mid] > target) {
            right = mid - 1;
        }
        // 否则，缩小搜索范围到右半部分
        else {
            left = mid + 1;
        }
    }

    // 没有找到目标，返回一个表示找不到的位置（通常设置为数组长度）
    return arr.size();
}

// 在主程序中使用
int main() {
    // 假设我们有一个已排序的整数数组
    std::vector<int> sortedArray = {1, 3, 5, 7, 9, 11, 13};

    // 输入要查找的目标值
    int searchValue;
    std::cout << "Enter a value to search: ";
    std::cin >> searchValue;

    // 使用二分查找函数查找目标值并输出位置
    size_t position = binarySearch(sortedArray, searchValue);
    if (position != std::vector<int>::npos) {
        std::cout << "Target value found at index: " << position << std::endl;
    } else {
        std::cout << "Target value not found in the array." << std::endl;
    }

    return 0;
}