LeetCode C++ 编译器问题。退货无效

Question

我现在正在学习C++，并从LeetCode中的任务开始。任务是二进制搜索。找到目标时返回语句出现问题。这是我的解决方案：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int mid = nums.size() / 2;
        while (mid < nums.size() && mid >= 0) {
            cout << mid << ' ' << nums[mid] << endl; //for debuging
            if (nums[mid] == target) {
                cout << "WTF";    //PRINTS
                return mid;       // Doesn't work!
            }
            else if (target > nums[mid]) {
                mid += mid / 2;
            } 
            else if (target < nums[mid]) {
                mid -= mid / 2;
            } 
        }
        return -1;
    }
};

问题出在

return mid;

。测试用例 [-1,0,3,5,9,12], target=9 的输出是

Time Limit Exceeded
2 5
3 9
WTF3 5
2 3
1 0
1 0
1 0
1 0...

因此，if 语句有效，但函数在 return 命令后继续工作。我尝试用 g++ 编译相同的代码，一切正常。

Answer 1

你的功能实现是错误的。例如，当向量

nums

只包含一个元素时，变量

mid

将不会改变

else if (target > nums[mid]) {
    mid += mid / 2;
} 
else if (target < nums[mid]) {
    mid -= mid / 2;
}

因为表达式

mid / 2

等于

0

。结果你将有一个无限循环。

功能可以通过以下方式实现

class Solution {
public:
    std::vector<int>::size_type search( const std::vector<int> &nums, int target ) 
    {
        std::vector<int>::size_type low = 0, high = nums.size();

        while ( low != high ) 
        {
            auto mid = low + ( high - low ) / 2;

            if ( target < nums[mid] ) 
            {
                high = mid;
            }
            else if ( nums[mid] < target ) 
            {
                low = mid + 1;
            } 
            else
            { 
                return mid;
            } 
        }

        return -1;
    }
};