GESP 五级 · GESP 202412 C++ 五级 第 11 题

给定一个长度为 $n$ 的有序数组 nums，其中所有元素都是唯一的。下面的函数返回数组中元素 target 的索引。

int binarySearch(vector<int> &nums, int target, int left, int right) {
    if (left > right) {
        return -1;
    }

    int middle = left + ((right - left) / 2);
    if (nums[middle] == target) {
        return middle;
    }
    else if (nums[middle] < target) {
        return binarySearch(nums, target, middle + 1, right);
    }
    else
        return binarySearch(nums, target, left, middle - 1);
}

int Find(vector<int> &nums, int target) {
    int n = nums.size();
    return binarySearch(nums, target, 0, n - 1);
}

关于上述函数，描述不正确的是（ ）。

分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】二分查找｜递归终止条件｜时间复杂度

1. 🎯 考纲定位（考点定位）

本题考查《GESP 五级大纲》算法模块的二分查找与递归过程分析。命题人专门把这道题放在五级，卡住的是那些只背"二分查找是 O(log n)"却说不清递归如何终止的考生——他们把"找到就返回"和"没找到会无限递归"混为一谈。