Search in Rotated Sorted Array in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a rotated sorted array?

A rotated sorted array is an array that was originally sorted in ascending order but then rotated (shifted) at some pivot point. For example, [4,5,6,7,0,1,2] is a rotated version of [0,1,2,4,5,6,7].

beginner

Why can't we use simple binary search directly on a rotated sorted array?

Because the array is not fully sorted in ascending order due to rotation, simple binary search may fail. We need to identify which part of the array is sorted to decide where to search next.

intermediate

In the search algorithm for a rotated sorted array, how do we decide which half to search next?

We check if the left half is sorted by comparing the start and middle elements. If sorted, we check if the target lies in this half. Otherwise, we search the other half. If the left half is not sorted, the right half must be sorted, and we do the same check there.

beginner

What is the time complexity of searching in a rotated sorted array using the modified binary search?

The time complexity is O(log n) because each step halves the search space, similar to regular binary search.

beginner

Java method signature to search target in rotated sorted array: public int search(int[] nums, int target). What does it return if target is not found?

It returns -1 to indicate the target is not present in the array.

What is the first step in searching a target in a rotated sorted array?

A Search linearly from start

B Sort the array again

C Check which half of the array is sorted

D Reverse the array

We first check which half is sorted to decide where to search next.

If the left half of the array is sorted and the target is within its range, where should we search next?

A In the right half

B At the start only

C At the middle only

D In the left half

If the left half is sorted and target lies there, we search in the left half.

What is the worst-case time complexity of searching in a rotated sorted array using binary search?

A O(n)

B O(log n)

C O(n log n)

D O(1)

The modified binary search halves the search space each time, so O(log n).

If the target is not found in the rotated sorted array, what should the search function return?

A -1

B 0

C null

D Array length

Returning -1 indicates the target is not present.

Which of these arrays is a rotated sorted array?

A [3,4,5,1,2]

B [1,2,3,4,5]

C [5,4,3,2,1]

D [2,1,3,4,5]

Array [3,4,5,1,2] is a rotated version of sorted array [1,2,3,4,5].

Explain step-by-step how to search for a target in a rotated sorted array using binary search.

Think about how rotation affects sorting and how to use that to guide search.

Describe why a rotated sorted array requires a modified binary search instead of a normal binary search.

Focus on the effect of rotation on array order.

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