Search in a Rotated Sorted Array II, thesarfo

Same problem as Search in a Rotated Sorted Array, but nums may contain duplicates — return true/false. (LeetCode 81) Duplicates make it ambiguous which half is sorted whenever nums[low] == nums[mid] == nums[high]. When that happens, shrink the search space from both ends (low++, high--) instead of trying to decide, then continue as before.

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int low = 0, high = nums.size() - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;

            if (nums[mid] == target) return true;

            // Handle duplicates: if nums[low] == nums[mid] == nums[high], we can't determine the sorted half.
            if (nums[low] == nums[mid] && nums[mid] == nums[high]) {
                low++;
                high--;
                continue;
            }

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

        return false;
    }
};

Time: O(log n) typically, degrading to O(n) with many duplicates. Space: O(1).