Search in Rotated Sorted Array

Java Coding Interview Track

Binary Search — Lesson 05

---

Ordered Lessons

#	Lesson
01	Binary Search
02	Search Insert Position
03	First Last Position
04	Find Peak Element
05	Search in Rotated Sorted Array ←
06	Binary Search Interview

---

Problem Statement

Suppose an array sorted in ascending order is rotated at an unknown pivot.

For example,

Original

0 1 2 4 5 6 7

After rotation,

4 5 6 7 0 1 2

Given the rotated sorted array and a target value, return its index.

If the target does not exist, return:

-1

The solution must run in O(log n) time.

---

Example 1

Input

nums = [4,5,6,7,0,1,2]

target = 0

Output

4

---

Example 2

Input

nums = [4,5,6,7,0,1,2]

target = 3

Output

-1

---

Example 3

Input

nums = [1]

target = 0

Output

-1

---

Understanding Rotation

Original

0 1 2 4 5 6 7

Rotated

4 5 6 7 0 1 2

Notice:

• The array is no longer globally sorted.
• However, at least one half is always sorted.

This observation is the key to solving the problem using Binary Search.

---

Visualization

4 5 6 7 0 1 2

      ↑

     Mid

Left Half

4 5 6 7

Sorted

Right Half

0 1 2

Rotated

---

Key Observation

At every iteration:

Either

Left Half

is sorted

or

Right Half

is sorted

Determine which half is sorted, then decide whether the target lies within that sorted range.

---

Algorithm

left = 0

right = n-1

while(left <= right)

    mid

    target found?

        return mid

    Left sorted?

        target inside?

            search left

        else

            search right

    Right sorted?

        target inside?

            search right

        else

            search left

Return -1

---

Dry Run

Input

4 5 6 7 0 1 2

Target = 0

Iteration 1

left = 0

right = 6

mid = 3

nums[mid] = 7

Left side

4 5 6 7

Sorted

Target

0

Not inside

Move Right

---

Iteration 2

0 1 2

mid = 5

nums[mid] = 1

Right side

0 1 2

Sorted

Target

0

Move Left

---

Iteration 3

mid = 4

nums[mid] = 0

Found

Return

4

---

Java Solution

public class SearchRotatedArray {

    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;
            }

            // Left half is sorted
            if (nums[left] <= nums[mid]) {

                if (target >= nums[left] &&
                    target < nums[mid]) {

                    right = mid - 1;

                } else {

                    left = mid + 1;

                }

            }

            // Right half is sorted
            else {

                if (target > nums[mid] &&
                    target <= nums[right]) {

                    left = mid + 1;

                } else {

                    right = mid - 1;

                }

            }

        }

        return -1;

    }

    public static void main(String[] args) {

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

        System.out.println(search(nums,0));

    }

}

---

Complexity Analysis

Operation	Complexity
Time	O(log n)
Space	O(1)

---

Decision Tree

graph TD
    Target_Found["Target Found?"] --> Yes["Yes"]
    Yes["Yes"] --> Return["Return"]
    Return["Return"] --> No["No"]
    No["No"] --> Left_Sorted["Left Sorted?"]
    Left_Sorted["Left Sorted?"] --> Yes["Yes"]
    Yes["Yes"] --> Target_Inside["Target Inside?"]
    Target_Inside["Target Inside?"] --> Yes["Yes"]
    Yes["Yes"] --> Search_Left["Search Left"]
    Search_Left["Search Left"] --> No["No"]
    No["No"] --> Search_Right["Search Right"]
    Search_Right["Search Right"] --> N_["---------------------"]
    N_["---------------------"] --> Right_Sorted["Right Sorted?"]
    Right_Sorted["Right Sorted?"] --> Target_Inside["Target Inside?"]
    Target_Inside["Target Inside?"] --> Yes["Yes"]
    Yes["Yes"] --> Search_Right["Search Right"]
    Search_Right["Search Right"] --> No["No"]
    No["No"] --> Search_Left["Search Left"]

---

Why Does It Work?

Even after rotation,

one half remains sorted.

We use the sorted half to determine whether the target can exist there.

This eliminates half of the search space in every iteration, preserving the O(log n) complexity.

---

Production Use Cases

Circular Buffers

Searching data in rotated ring buffers.

---

Log Rotation

Finding records after rotated log files.

---

Distributed Databases

Searching partitioned and rotated index segments.

---

Scheduling Systems

Searching rotated time-slot arrays.

---

Cache Systems

Searching circular cache structures.

---

IoT Devices

Searching rotated sensor history maintained in circular arrays.

---

Common Mistakes

Treating It as Normal Binary Search

The entire array is not sorted.

---

Forgetting to Identify the Sorted Half

Always check:

nums[left] <= nums[mid]

---

Wrong Boundary Conditions

Incorrect comparisons can skip the target.

Be careful with:

>=

<=

---

Ignoring Single Element Arrays

Always test:

[1]

---

Overflow

Use

left + (right-left)/2

instead of

(left+right)/2

---

Interview Tips

Mention these key observations:

• A rotated array always has one sorted half.
• Binary Search still works by identifying the sorted region.
• Time complexity remains O(log n).
• This solution assumes distinct values. If duplicates are allowed, additional handling is required.

---

Related Problems

• Binary Search
• Find Minimum in Rotated Sorted Array
• Search in Rotated Sorted Array II
• Peak Element
• Mountain Array Search
• Binary Search on Answer

---

Interview Questions

1. What is a rotated sorted array?

Answer

A rotated sorted array is a sorted array whose elements have been shifted around a pivot while maintaining the relative order within each segment.

---

2. Why does Binary Search still work?

Answer

Although the entire array is not sorted, one half is always sorted. This property allows us to eliminate half of the search space during each iteration.

---

3. What is the time complexity?

Answer

O(log n) because the search space is halved at every step.

---

4. What is the space complexity?

Answer

O(1) for the iterative implementation.

---

5. How do we identify the sorted half?

Answer

If nums[left] <= nums[mid], the left half is sorted. Otherwise, the right half is sorted.

---

6. What happens if duplicates exist?

Answer

With duplicates, identifying the sorted half may become ambiguous. Additional logic is needed, as in Search in Rotated Sorted Array II.

---

7. Why do we compare the target with boundary values?

Answer

The boundary values determine whether the target lies within the sorted half. If it does, we search that half; otherwise, we search the other half.

---

8. Where is this pattern used in production?

Answer

Circular buffers, log rotation, distributed indexing, scheduling systems, cache management, and IoT data structures.

---

9. What are the most common mistakes?

Answer

Treating the array as fully sorted, choosing the wrong half, incorrect boundary comparisons, and failing to handle edge cases.

---

10. Which problems are closely related?

Answer

Find Minimum in Rotated Sorted Array, Search in Rotated Sorted Array II, Peak Element, Mountain Array Search, and Binary Search on Answer.

---

Quick Revision

Concept	Value
Pattern	Modified Binary Search
Key Observation	One half is always sorted
Time Complexity	O(log n)
Space Complexity	O(1)
Handles Rotation	Yes
Handles Duplicates	No (basic version)
Interview Frequency	⭐⭐⭐⭐⭐

---

Key Takeaways

• A rotated sorted array is not globally sorted, but one half remains sorted in every iteration.
• Identifying the sorted half allows Binary Search to eliminate half of the search space.
• The algorithm maintains O(log n) time and O(1) space complexity.
• Careful boundary comparisons are essential to avoid skipping the target.
• This problem is a foundational interview question that leads to more advanced Binary Search variations involving rotations and duplicates.

---