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

> Master binary search on a rotated sorted array in Java. Find targets in O(log n) time by identifying sorted halves and narrowing the search space efficiently.

- Repository: [Kevin Naughton Jr./interviews](https://github.com/kdn251/interviews)
- Tags: how-to-guide
- Published: 2026-03-04

---

**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`](https://github.com/kdn251/interviews/blob/main/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`](https://github.com/kdn251/interviews/blob/main/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:

```java
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`](https://github.com/kdn251/interviews/blob/main/leetcode/array/SearchInRotatedSortedArray.java) — The primary reference implementation containing the core loop on lines 14–36.
- [`company/uber/SearchInRotatedSortedArray.java`](https://github.com/kdn251/interviews/blob/main/company/uber/SearchInRotatedSortedArray.java) — Identical implementation packaged for Uber interview scenarios.
- [`company/linkedin/SearchInRotatedSortedArray.java`](https://github.com/kdn251/interviews/blob/main/company/linkedin/SearchInRotatedSortedArray.java) — LinkedIn-specific packaging of the same algorithm.
- [`company/facebook/SearchInRotatedSortedArray.java`](https://github.com/kdn251/interviews/blob/main/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`](https://github.com/kdn251/interviews/blob/main/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`](https://github.com/kdn251/interviews/blob/main/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`](https://github.com/kdn251/interviews/blob/main/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.