How to Perform Binary Search on a Rotated Sorted Array in Java

You can locate a target value in O(log n) time by determining which half of the array remains sorted, testing whether the target falls within that sorted range, and repeatedly halving the search space until the target is found or the interval empties.

The kdn251/interviews repository provides a robust Java implementation that demonstrates how to perform binary search on a rotated sorted array without knowing the pivot location. This technique adapts the classic divide-and-conquer approach to handle the structural change introduced by the rotation, maintaining logarithmic efficiency while searching for a target value in a shifted ascending sequence.

Understanding the Rotated Sorted Array Problem

In a standard binary search, the entire array is sorted, allowing you to compare the target directly with the middle element to eliminate half of the remaining elements. When an array is rotated, this global property breaks, but local sortedness remains: at any given index, either the left or the right half must still be in ascending order because the rotation disrupts the sequence at only a single boundary.

This invariant is the key insight that enables O(log n) search performance. By identifying which half is sorted and checking whether your target lies within its bounds, you can safely discard the other half regardless of its contents.

The Modified Binary Search Algorithm

The implementation in leetcode/array/SearchInRotatedSortedArray.java (lines 14–36) follows a disciplined three-step process at each iteration.

Core Logic and Invariants

The algorithm initializes two pointers, left = 0 and right = nums.length - 1, representing the current search bounds. While left <= right, it calculates mid = left + (right - left) / 2 to avoid integer overflow.

If nums[mid] equals the target, the search terminates immediately. Otherwise, the algorithm determines which side of mid is sorted:

• Left half sorted: When nums[left] <= nums[mid], the elements from left to mid form a continuous ascending sequence. The algorithm checks if the target lies between nums[left] and nums[mid]. If so, it sets right = mid - 1 to search left; otherwise, it sets left = mid + 1 to search right.
• Right half sorted: When nums[mid] <= nums[right], the algorithm performs the symmetric check, narrowing to left = mid + 1 if the target is within the right sorted bounds, or to right = mid - 1 otherwise.

This logic handles all edge cases—including single-element arrays, unrotated arrays, and targets located at array boundaries—because it never assumes a specific pivot location and validates indices before accessing them.

Source Code Reference

According to the repository structure, the search method in SearchInRotatedSortedArray.java implements exactly this decision tree. The method signature accepts an int[] nums array and an int target, returning the index of the target or -1 if absent.

Complete Java Implementation

The following runnable example demonstrates how to instantiate the solver and execute searches against a rotated array:

public class Demo {
    public static void main(String[] args) {
        SearchInRotatedSortedArray solver = new SearchInRotatedSortedArray();
        
        int[] nums = {4, 5, 6, 7, 0, 1, 2};
        
        // Target exists in the array
        int index1 = solver.search(nums, 0);   // Returns 4
        System.out.println(index1);
        
        // Target does not exist
        int index2 = solver.search(nums, 3);   // Returns -1
        System.out.println(index2);
    }
}

The search method returns the zero-based index of the target value if present, or -1 if the target is absent from the array.

File Structure and Repository Organization

The kdn251/interviews repository replicates this solution across multiple packages to support interview preparation for specific companies:

• leetcode/array/SearchInRotatedSortedArray.java — The primary reference implementation containing the core loop on lines 14–36.
• company/uber/SearchInRotatedSortedArray.java — Identical implementation packaged for Uber interview scenarios.
• company/linkedin/SearchInRotatedSortedArray.java — LinkedIn-specific packaging of the same algorithm.
• company/facebook/SearchInRotatedSortedArray.java — Facebook interview preparation version.

Each file maintains the same method signature and logic, ensuring consistent behavior across different interview contexts.

Summary

• Binary search on a rotated sorted array achieves O(log n) time complexity by exploiting the fact that at least one half of any sub-array remains sorted after rotation.
• The algorithm determines which half is sorted by comparing nums[left] with nums[mid], then checks whether the target falls within that sorted range to decide which half to discard.
• The reference implementation in leetcode/array/SearchInRotatedSortedArray.java handles all edge cases, including single-element inputs and targets at array boundaries, without requiring knowledge of the pivot index.
• Identical copies exist under company/uber/, company/linkedin/, and company/facebook/ for structured interview practice.

Frequently Asked Questions

What is the time complexity of binary search on a rotated sorted array?

The algorithm runs in O(log n) time, where n is the length of the array. At each iteration, it eliminates exactly half of the remaining elements by determining which side is sorted and whether the target could exist there, mirroring the efficiency of standard binary search.

How do you identify which half of a rotated sorted array is sorted?

You compare the leftmost element with the middle element. If nums[left] <= nums[mid], the left half is sorted; otherwise, the right half must be sorted because there is only one rotation point. This comparison works because a sorted half will always have its start value less than or equal to its end value.

Does this algorithm work if the array contains duplicate elements?

The standard implementation in SearchInRotatedSortedArray.java assumes distinct elements or typical LeetCode constraints where duplicates are not present. If duplicates exist (e.g., nums[left] == nums[mid] == nums[right]), the algorithm may degrade to O(n) in the worst case because it cannot determine which half is sorted when endpoints are equal, requiring a linear fallback.

Where can I find the reference implementation in the kdn251/interviews repository?

The primary implementation is located at leetcode/array/SearchInRotatedSortedArray.java. Additional copies for company-specific interview preparation are available under company/uber/, company/linkedin/, and company/facebook/ within the same repository structure.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}