LeetCode 81题C++代码返回错误，求二分查找修正方案

问题分析 #

你的代码核心问题在于错误地尝试拆分旋转数组，嵌套循环的拆分逻辑完全混乱，不仅没正确分离出两个有序子数组，还初始化了固定大小的f和x向量，导致二分查找时访问到初始的空元素，直接引发测试用例的错误：

• 测试用例[1]中，f[0]是初始化的0，判断target==f[0]时1≠0，直接进入后续分支，而后续二分的数组都是无效的初始元素，最终返回false；
• 测试用例[1]找0时，x[0]是初始化的0，错误返回true；
• 测试用例[2,5,6,0,0,1,2]找2时，拆分逻辑错误导致f和x数组完全不对，二分自然找不到目标。

此外，你的实现完全偏离了旋转数组二分查找的核心思路——不需要拆分数组，直接在原数组上通过判断区间有序性来缩小二分范围。

修正后的二分查找代码 #

以下是符合要求的C++实现，直接在原数组上进行二分，处理重复元素的情况：

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2; // 避免整数溢出
            if (nums[mid] == target) {
                return true;
            }
            // 左半部分有序（含重复判断）
            if (nums[mid] > nums[left]) {
                // 判断target是否在左半有序区间内
                if (target >= nums[left] && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else if (nums[mid] < nums[left]) {
                // 右半部分有序
                if (target > nums[mid] && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            } else {
                // nums[mid] == nums[left]，无法判断区间有序性，缩小左边界
                left++;
            }
        }
        return false;
    }
};

代码说明 #

1. 溢出规避：用left + (right - left)/2代替(left+right)/2，防止大数相加导致的整数溢出；
2. 区间有序判断：
   • 当nums[mid] > nums[left]，左半区间[left, mid]严格有序，判断target是否在该区间内调整边界；
   • 当nums[mid] < nums[left]，右半区间[mid, right]严格有序，同理调整边界；
   • 当nums[mid] == nums[left]，因重复元素无法确定区间有序性，仅将left右移一位缩小查找范围；
3. 终止逻辑：找到target直接返回true，循环结束未找到则返回false。

测试用例验证 #

• 输入[2,5,6,0,0,1,2]、target=2：mid会命中元素2，返回true；
• 输入[1]、target=1：mid=0时匹配target，返回true；
• 输入[1]、target=0：循环结束未找到目标，返回false。

内容的提问来源于stack exchange，提问作者hailice