Search in Rotated Sorted Array in DSA Java - Build from Scratch

Search in Rotated Sorted Array

📖 Scenario: You have a list of numbers that was originally sorted but then rotated at some unknown point. For example, [4,5,6,7,0,1,2] is a rotated version of [0,1,2,4,5,6,7]. You want to find if a specific number exists in this rotated list.

🎯 Goal: Build a Java program that searches for a target number in a rotated sorted array and returns its index or -1 if not found.

📋 What You'll Learn

Create an integer array called nums with the exact values {4,5,6,7,0,1,2}.

Create an integer variable called target and set it to 0.

Write a method called search that takes an integer array nums and an integer target, and returns the index of target in nums or -1 if not found.

Use binary search logic adapted for rotated sorted arrays inside the search method.

Print the result of search(nums, target).

💡 Why This Matters

🌍 Real World

Searching in rotated sorted arrays is common in systems where data is shifted or rotated, such as circular buffers or rotated logs.

💼 Career

Understanding this search technique helps in technical interviews and in optimizing search operations in rotated or shifted datasets.

1

Create the rotated sorted array

Create an integer array called nums with the exact values {4,5,6,7,0,1,2}.

DSA Java

# Your code here

Hint

Use int[] nums = {4,5,6,7,0,1,2}; to create the array.

2

Set the target number to search

Create an integer variable called target and set it to 0.

DSA Java

int[] nums = {4,5,6,7,0,1,2};
# Your code here

Hint

Use int target = 0; to set the target.

3

Write the search method using binary search logic

Write a method called search that takes an integer array nums and an integer target, and returns the index of target in nums or -1 if not found. Use binary search logic adapted for rotated sorted arrays inside the search method.

DSA Java

int[] nums = {4,5,6,7,0,1,2};
int target = 0;

// Write the search method below
# Your code here

Hint

Use a while loop with left and right pointers and check which side is sorted to decide where to search next.

4

Print the search result

Print the result of search(nums, target).

DSA Java

int[] nums = {4,5,6,7,0,1,2};
int target = 0;

public static int search(int[] nums, int target) {
    int left = 0;
    int 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;
}

// Print the result below
# Your code here

Hint

Use System.out.println(search(nums, target)); inside the main method to print the index.

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