Search in Rotated Sorted Array in Java: Explanation & Practice

Binary search in rotated array

Problem summary

Given a rotated sorted array (e.g., [4,5,6,7,0,1,2] from [0,1,2,4,5,6,7]), search for target. Maintain O(log n) complexity.

Starter code

public class Main {
    public static void main(String[] args) {
        int[] nums = {4, 5, 6, 7, 0, 1, 2};
        int target = 0;
        
        // At least one half is always sorted
        // Check which half is sorted
        // Determine which half target belongs to
        // Print: Index: 4
    }
}

Expected output and test cases

[4,5,6,7,0,1,2], target=0
```
Index: 4
```
[4,5,6,7,0,1,2], target=3
```
Index: -1
```
[3,1], target=1
```
Index: 1
```

Hints

In a rotated sorted array, one half is always sorted
Compare nums[left] with nums[mid] to find sorted half
Check if target is in sorted half's range
If yes, search there; otherwise search other half

Related Data Structures & Algorithms exercises

Practice all Data Structures & Algorithms exercises · Run this idea in the Java compiler