本文共 1582 字，大约阅读时间需要 5 分钟。

要解决这个问题，我们需要找到一个目标值在一个被旋转的已排序数组中。由于数组被旋转，传统的二分查找方法可能不适用。我们可以通过比较中间元素和右边元素的值来调整查找范围。

方法思路

解决代码

public boolean search(vector
   
     nums, int target) {
    if (nums.empty()) {
        return false;
    }
    int left = 0;
    int right = nums.size() - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return true;
        }
        if (nums[mid] > nums[right]) {
            // 左边可能有序，右边可能有序
            if (target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else if (nums[mid] < nums[right]) {
            // 右边可能有序
            if (target > nums[mid]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        } else {
            // nums[mid] == nums[right]
            // 继续检查右边的部分
            if (nums[right] == target) {
                return true;
            } else {
                right = mid - 1;
            }
        }
    }
    return nums[left] == target || nums[right] == target;
}
   

代码解释

• 初始化：检查数组为空，返回false。初始化左指针为0，右指针为数组末尾。
• 循环处理：在数组有序时，计算中间元素。比较中间元素和右边元素的值，决定左或右指针的调整方向。
• 条件判断：
  • 如果中间元素等于目标值，返回true。
  • 如果中间元素大于右边元素，调整指针以缩小查找范围。
  • 如果中间元素小于右边元素，调整指针以缩小查找范围。
  • 如果中间元素等于右边元素，继续检查右边部分。
• 终止条件：当指针相交时，检查边界元素是否为目标值，返回结果。

这种方法确保了在旋转数组中高效地查找目标值，时间复杂度为O(log n)。