LeetCode 81. Search in Rotated Sorted Array II

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

Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums.

You must decrease the overall operation steps as much as possible.

 Example 1:

Input: nums = [2,5,6,0,0,1,2], target = 0

Output: true

Example 2:

Input: nums = [2,5,6,0,0,1,2], target = 3

Output: false

Example 3: EDGE CASE

Input: nums = [3,3,1,2,3,3,3], target = 1

Output: true

package LeetCode.binarySearch;

public class LT81_SearchInRotatedSortedArray2 {

    public static void main(String[] args) {
        int[] arr = {3, 3, 1, 2, 3, 3, 3};

        int target = 0;

        boolean idx = search(arr, target);
        System.out.println(idx);

    }

    /**
     * Time Complexity:
     * - Best / Average Case: O(log n), due to binary search.
     * - Worst Case: O(n), when duplicates force linear scan (e.g., [1,1,1,1,1,1,2,1]).
     * Space Complexity: O(1), constant space used.
     */
    public static boolean search(int[] nums, int target) {
        int low = 0, high = nums.length - 1;

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

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

            // Handle duplicates on both ends
            if (nums[low] == nums[mid] && nums[mid] == nums[high]) {
                low++;
                high--;
            }
            // Left half is sorted
            else if (nums[low] <= nums[mid]) {
                if (nums[low] <= target && target < nums[mid])
                    high = mid - 1;
                else
                    low = mid + 1;
            }
            // Right half is sorted
            else {
                if (nums[mid] < target && target <= nums[high])
                    low = mid + 1;
                else
                    high = mid - 1;
            }
        }

        return false;
    }

}

Case	Time Complexity	Space Complexity	Explanation
Best	O(1)	O(1)	Target found at the middle index in the first comparison.
Average	O(log n)	O(1)	Normal binary search behavior when duplicates are minimal or non-impactful.
Worst	O(n)	O(1)	When duplicates prevent binary decision, forcing linear reduction (e.g., [1,1,1,1,2,1]).

Example: WORST CASE EG.

int[] nums = {2, 2, 2, 2, 3, 2, 2};

int target = 3;

👇 What happens during binary search:

1. Initial State:

   low = 0, high = 6, mid = 3
   nums[mid] = 2, nums[low] = 2, nums[high] = 2
   

   • Since nums[low] == nums[mid] == nums[high], we can't tell which side is sorted.

   • So we do:

     low++, high--;

   • This continues, narrowing the range one step at a time, just like linear search.

2. This repeats until we find 3 or exhaust the array.

⚠️ Why This Is Bad:

• Because we can't divide the array in half using binary logic due to all elements being the same.

• So we reduce low and high by 1 each time — leading to O(n) time.