Search in Rotated Sorted Array in DSA Java - Time & Space Complexity

Time Complexity: Search in Rotated Sorted Array

O(log n)

Understanding Time Complexity

We want to understand how fast we can find a number in a rotated sorted list.

How does the time to search grow as the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public int 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 mid;
        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 -1;
}

This code searches for a target number in a rotated sorted array using a modified binary search.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that halves the search range each time.
• How many times: The loop runs until the search range is empty, roughly halving the range each time.

How Execution Grows With Input

Each step cuts the search space in half, so the number of steps grows slowly as the list grows.

Input Size (n)	Approx. Operations
10	About 4 to 5 steps
100	About 7 steps
1000	About 10 steps

Pattern observation: Doubling the list size adds only one extra step.

Final Time Complexity

Time Complexity: O(log n)

This means the search time grows slowly, adding just a few more steps even if the list gets much bigger.

Common Mistake

[X] Wrong: "Because the array is rotated, we must check every element, so it takes linear time."

[OK] Correct: The code cleverly uses the sorted parts to skip half the list each time, keeping the search fast.

Interview Connect

Understanding this search shows you can adapt classic methods to tricky situations, a skill valued in real problems.

Self-Check

"What if the array was not rotated but still sorted? How would the time complexity change?"

Practice

1. What is the main challenge when searching for an element in a rotated sorted array compared to a normal sorted array?

easy

A. The array elements are all negative numbers.

B. The array contains duplicate elements which confuse the search.

C. The array is not fully sorted, so normal binary search cannot be directly applied.

D. The array size is unknown, so we cannot set search boundaries.

Solution

1. Step 1: Understand normal binary search assumption

   Binary search works efficiently only if the array is fully sorted in ascending or descending order.

2. Step 2: Identify the effect of rotation

   Rotation breaks the full sorted order, splitting the array into two sorted parts, so normal binary search fails without modification.

3. Final Answer:

   The array is not fully sorted, so normal binary search cannot be directly applied. -> Option C

4. Quick Check:

   Rotated array breaks full sort = normal binary search fails [OK]

Hint: Rotation breaks full sort; adjust binary search accordingly [OK]

Common Mistakes:

• Assuming array is fully sorted and applying normal binary search
• Ignoring rotation and searching linearly
• Confusing rotation with duplicates

2. Which of the following is the correct Java method signature to implement binary search in a rotated sorted array?

easy

A. int search(int nums[], target)

B. public int search(int[] nums, int target)

C. public void search(int[] nums, int target)

D. int search(int[] nums, int target, int start, int end)

Solution

1. Step 1: Check Java method signature conventions

   Java methods must specify access modifier, return type, method name, and parameter types with names.

2. Step 2: Analyze each option

   public int search(int[] nums, int target) correctly declares a public method returning int with parameters int[] and int. int search(int nums[], target) misses return type and parameter type for target. public void search(int[] nums, int target) returns void but search should return index. int search(int[] nums, int target, int start, int end) has extra parameters but no access modifier.

3. Final Answer:

   public int search(int[] nums, int target) -> Option B

4. Quick Check:

   Correct Java method signature = public int search(int[] nums, int target) [OK]

Hint: Java method needs return type and parameter types correctly [OK]

Common Mistakes:

• Omitting return type
• Missing parameter types
• Using void instead of int return type

3. What will be the output of the following Java code snippet?

public class RotatedSearch {
    public static int 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 mid;
            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 -1;
    }
    public static void main(String[] args) {
        int[] arr = {4,5,6,7,0,1,2};
        System.out.println(search(arr, 0));
    }
}

medium

A. 4

B. 0

C. -1

D. 6

Solution

1. Step 1: Understand the array and target

   The array is rotated sorted: [4,5,6,7,0,1,2]. Target is 0, which is at index 4.

2. Step 2: Trace the binary search steps

   Initial left=0, right=6, mid=3 (value 7). Left half is sorted (4 to 7). Target 0 is not in left half, so move left=mid+1=4. Now left=4, right=6, mid=5 (value 1). Right half is sorted (1 to 2). Target 0 is less than nums[mid], so move right=mid-1=4. Now left=4, right=4, mid=4 (value 0). Found target at index 4.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   Target 0 found at index 4 [OK]

Hint: Check which half is sorted to decide search direction [OK]

Common Mistakes:

• Not updating left/right correctly
• Confusing indices after rotation
• Returning wrong index or -1 incorrectly

4. Identify the bug in the following Java method for searching in a rotated sorted array:

public int 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 mid;
        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 -1;
}

medium

A. The loop condition should be 'left <= right' instead of 'left < right'.

B. The mid calculation is incorrect and may cause overflow.

C. The method should return void instead of int.

D. The array should be sorted before searching.

Solution

1. Step 1: Analyze loop condition

   The loop uses 'while (left < right)', which misses the case when left == right, possibly skipping the last element check.

2. Step 2: Correct loop condition for binary search

   Binary search requires 'while (left <= right)' to ensure all elements are checked, including when left equals right.

3. Final Answer:

   The loop condition should be 'left <= right' instead of 'left < right'. -> Option A

4. Quick Check:

   Loop must include equality to check all elements [OK]

Hint: Use 'left <= right' in binary search loops [OK]

Common Mistakes:

• Using 'left < right' and missing last element
• Incorrect mid calculation causing overflow
• Returning wrong type or ignoring array rotation

5. Given a rotated sorted array with possible duplicates, which modification is needed in the binary search algorithm to correctly find the target?

hard

A. Ignore duplicates and apply normal rotated binary search

B. Use linear search instead of binary search

C. Sort the array before searching

D. Skip duplicates by incrementing left when nums[left] == nums[mid] == nums[right]

Solution

1. Step 1: Understand duplicates effect on rotated binary search

   Duplicates can make it unclear which half is sorted because nums[left], nums[mid], and nums[right] may be equal.

2. Step 2: Modify search to handle duplicates

   When nums[left] == nums[mid] == nums[right], increment left by 1 to skip duplicates and reduce search space safely.

3. Final Answer:

   Skip duplicates by incrementing left when nums[left] == nums[mid] == nums[right] -> Option D

4. Quick Check:

   Skip duplicates to maintain binary search correctness [OK]

Hint: Skip duplicates when ends equal to avoid confusion [OK]

Common Mistakes:

• Ignoring duplicates causing infinite loops
• Switching to linear search unnecessarily
• Sorting array breaks problem constraints