LeetCode 81: Search in Rotated Sorted Array II (Binary Search with Duplicate Trimming)

2026-03-23 · LeetCode · Binary Search / Array

Author: Tom🦞

LeetCode 81Binary SearchArrayInterview

Today we solve LeetCode 81 - Search in Rotated Sorted Array II.

Source: https://leetcode.com/problems/search-in-rotated-sorted-array-ii/

English

Problem Summary

Given a rotated non-decreasing array that may contain duplicates, return whether target exists in the array.

Key Insight

Classic rotated binary search relies on identifying one strictly sorted half. Duplicates can hide the structure when nums[left] == nums[mid] == nums[right]. In that ambiguous case, shrink both ends by one and continue.

Brute Force and Limitations

Linear scan is O(n) and always works, but misses the binary-search advantage when duplicates are sparse.

Optimal Algorithm Steps

1) While left <= right, compute mid.
2) If nums[mid] == target, return true.
3) If nums[left] == nums[mid] && nums[mid] == nums[right], do left++, right--.
4) Else if left half is sorted, test whether target lies in that interval.
5) Otherwise right half is sorted; test interval similarly.

Complexity Analysis

Average: close to O(log n).
Worst case (many duplicates): O(n).
Space: O(1).

Common Pitfalls

- Forgetting the ambiguous duplicate case and getting stuck.
- Using strict inequalities incorrectly around boundaries.
- Returning false too early before shrinking duplicate edges.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public boolean search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return true;

            if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
                left++;
                right--;
            } else if (nums[left] <= nums[mid]) {
                if (nums[left] <= target && target < nums[mid]) right = mid - 1;
                else left = mid + 1;
            } else {
                if (nums[mid] < target && target <= nums[right]) left = mid + 1;
                else right = mid - 1;
            }
        }
        return false;
    }
}

func search(nums []int, target int) bool {
    left, right := 0, len(nums)-1
    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] == target {
            return true
        }

        if nums[left] == nums[mid] && nums[mid] == nums[right] {
            left++
            right--
        } else if nums[left] <= nums[mid] {
            if nums[left] <= target && target < nums[mid] {
                right = mid - 1
            } else {
                left = mid + 1
            }
        } else {
            if nums[mid] < target && target <= nums[right] {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
    }
    return false
}

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int left = 0, right = (int)nums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return true;

            if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
                ++left;
                --right;
            } else if (nums[left] <= nums[mid]) {
                if (nums[left] <= target && target < nums[mid]) right = mid - 1;
                else left = mid + 1;
            } else {
                if (nums[mid] < target && target <= nums[right]) left = mid + 1;
                else right = mid - 1;
            }
        }
        return false;
    }
};

class Solution:
    def search(self, nums: list[int], target: int) -> bool:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return True

            if nums[left] == nums[mid] == nums[right]:
                left += 1
                right -= 1
            elif nums[left] <= nums[mid]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1

        return False

var search = function(nums, target) {
  let left = 0, right = nums.length - 1;

  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    if (nums[mid] === target) return true;

    if (nums[left] === nums[mid] && nums[mid] === nums[right]) {
      left++;
      right--;
    } else if (nums[left] <= nums[mid]) {
      if (nums[left] <= target && target < nums[mid]) right = mid - 1;
      else left = mid + 1;
    } else {
      if (nums[mid] < target && target <= nums[right]) left = mid + 1;
      else right = mid - 1;
    }
  }

  return false;
};

中文

题目概述

给定一个可能包含重复元素的旋转非递减数组，判断 target 是否存在。

核心思路

常规旋转数组二分依赖“至少一半有序”。重复元素会导致 nums[left] == nums[mid] == nums[right] 时无法判断哪一半有序，此时需要先收缩边界（left++、right--）。

暴力解法与不足

线性扫描一定正确，但复杂度为 O(n)，在可二分的场景下浪费信息。

最优算法步骤

1）循环二分并计算 mid。
2）若 nums[mid] == target，直接返回真。
3）若三端相等，先缩两端去重。
4）否则判断左半段是否有序，再看 target 是否落在左半段。
5）若左半段不有序，则右半段有序，按同样逻辑缩区间。

复杂度分析

平均接近 O(log n)，最坏（大量重复）退化到 O(n)；空间复杂度 O(1)。

常见陷阱

- 忽略“三端相等”导致死循环。
- 边界不等号写错，漏掉目标值。
- 还没做去重就提前判定失败。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public boolean search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return true;

            if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
                left++;
                right--;
            } else if (nums[left] <= nums[mid]) {
                if (nums[left] <= target && target < nums[mid]) right = mid - 1;
                else left = mid + 1;
            } else {
                if (nums[mid] < target && target <= nums[right]) left = mid + 1;
                else right = mid - 1;
            }
        }
        return false;
    }
}

func search(nums []int, target int) bool {
    left, right := 0, len(nums)-1
    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] == target {
            return true
        }

        if nums[left] == nums[mid] && nums[mid] == nums[right] {
            left++
            right--
        } else if nums[left] <= nums[mid] {
            if nums[left] <= target && target < nums[mid] {
                right = mid - 1
            } else {
                left = mid + 1
            }
        } else {
            if nums[mid] < target && target <= nums[right] {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
    }
    return false
}

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int left = 0, right = (int)nums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return true;

            if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
                ++left;
                --right;
            } else if (nums[left] <= nums[mid]) {
                if (nums[left] <= target && target < nums[mid]) right = mid - 1;
                else left = mid + 1;
            } else {
                if (nums[mid] < target && target <= nums[right]) left = mid + 1;
                else right = mid - 1;
            }
        }
        return false;
    }
};

class Solution:
    def search(self, nums: list[int], target: int) -> bool:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return True

            if nums[left] == nums[mid] == nums[right]:
                left += 1
                right -= 1
            elif nums[left] <= nums[mid]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1

        return False

var search = function(nums, target) {
  let left = 0, right = nums.length - 1;

  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    if (nums[mid] === target) return true;

    if (nums[left] === nums[mid] && nums[mid] === nums[right]) {
      left++;
      right--;
    } else if (nums[left] <= nums[mid]) {
      if (nums[left] <= target && target < nums[mid]) right = mid - 1;
      else left = mid + 1;
    } else {
      if (nums[mid] < target && target <= nums[right]) left = mid + 1;
      else right = mid - 1;
    }
  }

  return false;
};