如何在C++中实现一个具有O(logn)时间复杂度的搜索算法，并解释其工作原理？

在C++中实现一个具有O(logn)时间复杂度的搜索算法，通常是实现二分搜索算法。二分搜索算法适用于已排序的数组或集合，通过不断地将搜索区间分成两半来缩小搜索范围，直到找到目标元素或者确定元素不存在为止。以下是具体实现步骤和代码示例：

参考资源链接：[清华大学出版社C++版数据结构习题答案详解](https://wenku.csdn.net/doc/6zcvh1rszz?spm=1055.2569.3001.10343)

1. 确定数组是有序的。
2. 设定搜索范围的起始点low和终点high。
3. 计算中间点mid = (low + high) / 2。
4. 比较中间点的值与目标值：
- 如果相等，返回中间点的位置。
- 如果中间点的值大于目标值，调整搜索范围为前半部分，即设置high = mid - 1。
- 如果中间点的值小于目标值，调整搜索范围为后半部分，即设置low = mid + 1。
5. 重复步骤3和4直到low <= high。
6. 如果未找到目标值，返回一个指示未找到的标记（例如-1）。

示例代码：

    int binarySearch(const vector<int>& arr, int target) {
        int low = 0;
        int high = arr.size() - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] == target) {
                return mid; // 返回目标值的索引
            } else if (arr[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1; // 未找到目标值
    }

二分搜索算法的时间复杂度为O(logn)，这是因为每次比较将搜索空间减少一半。这种搜索算法不仅效率高，而且实现起来也相对简单。如果你希望深入理解数据结构和算法在实际中的应用，清华大学出版社出版的《清华大学出版社C++版数据结构习题答案详解》将为你提供详尽的解答和实用的示例。

参考资源链接：[清华大学出版社C++版数据结构习题答案详解](https://wenku.csdn.net/doc/6zcvh1rszz?spm=1055.2569.3001.10343)