Search in Rotated Sorted Array in DSA Java - Execution Trace

Concept Flow - Search in Rotated Sorted Array

Start with low=0, high=n-1

↓

Calculate mid = (low+high)/2

↓

Check if nums[mid

No↓

Check if left half sorted? nums[low

↓

Check if target in left half?

↓

Repeat loop

↓

If low > high, target not found

↓

Return -1

This flow shows how binary search adapts to a rotated sorted array by checking which half is sorted and narrowing the search accordingly.

Execution Sample

DSA Java

int search(int[] nums, int target) {
  int low = 0, high = nums.length - 1;
  while (low <= high) {
    int mid = (low + high) / 2;
    if (nums[mid] == target) return mid;
    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 -1;
}

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

Execution Table

Step	Operation	low	high	mid	nums[mid]	Check Sorted Half	Pointer Changes	Visual State
1	Initialize	0	6	-	-	-	-	[4,5,6,7,0,1,2]
2	Calculate mid	0	6	3	7	Left half sorted (4 <= 7)	-	[4,5,6,7,0,1,2]
3	Check target=0 in left half?	0	6	3	7	No (0 < 4 or 0 >= 7)	low = mid + 1 = 4	[4,5,6,7,0,1,2]
4	Calculate mid	4	6	5	1	Left half sorted (0 <= 1)	-	[4,5,6,7,0,1,2]
5	Check target=0 in left half?	4	6	5	1	No (0 < 0 or 0 >= 1)	high = mid - 1 = 4	[4,5,6,7,0,1,2]
6	Calculate mid	4	4	4	0	Left half sorted (0 <= 0)	-	[4,5,6,7,0,1,2]
7	nums[mid] == target?	4	4	4	0	Yes	Return 4	[4,5,6,7,0,1,2]
8	End	-	-	-	-	-	-	Target found at index 4

💡 Target found at index 4, search ends.

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 6	Final
low	0	4	4	4	4
high	6	6	4	4	4
mid	-	3	5	4	4
nums[mid]	-	7	1	0	0

Key Moments - 3 Insights

Why do we check if the left half is sorted using nums[low] <= nums[mid]?

Because in a rotated sorted array, one half is always sorted. Checking nums[low] <= nums[mid] tells us if the left half is sorted, so we know where to search next (see Step 2 in execution_table).

Why do we update low or high pointers differently based on target's position?

We narrow the search to the half where the target can be. If target lies within the sorted half, we adjust high or low to focus there. Otherwise, we search the other half (see Steps 3 and 5).

Why does the loop stop when low > high?

Because low > high means the search space is empty and target is not found. This is the exit condition for the binary search loop.

Visual Quiz - 3 Questions

Look at the execution_table at Step 3. What is the value of 'low' after this step?

A 4

B 0

C 3

D 6

💡 Hint

Check the 'Pointer Changes' column at Step 3 in the execution_table.

At which step does the algorithm find the target?

A Step 5

B Step 6

C Step 7

D Step 8

💡 Hint

Look for the step where 'nums[mid] == target' is true in the execution_table.

If the target was 3 instead of 0, what would happen to the 'high' pointer after Step 3?

A It would become 2

B It would become 6

C It would become 3

D It would become 4

💡 Hint

Refer to the condition in Step 3 and how 'low' and 'high' are updated based on target's position.

Concept Snapshot

Search in Rotated Sorted Array:
- Use binary search with low and high pointers.
- Find mid = (low + high) / 2.
- Check if left half (low to mid) is sorted.
- If target in sorted half, narrow search there.
- Else search the other half.
- Repeat until found or low > high.
- Return index or -1 if not found.

Full Transcript

This concept shows how to search a target in a rotated sorted array using a modified binary search. We start with low and high pointers at the array ends. Calculate mid index and check if nums[mid] equals target. If not, check if left half is sorted by comparing nums[low] and nums[mid]. If left half is sorted and target lies within it, move high pointer to mid - 1. Otherwise, move low pointer to mid + 1. If left half is not sorted, the right half must be sorted. Check if target lies in right half and adjust pointers accordingly. Repeat until target is found or search space is empty (low > high). Return the index if found, else -1. The execution table traces these steps with pointer values and array states. Key moments clarify why we check sorted halves and how pointers move. The visual quiz tests understanding of pointer updates and termination conditions.

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