Logo

Kode$word

Search in Rotated Sorted Array – Binary Search Explained with Java Solution (LeetCode 33)
Search in Rotated Sorted Array – Binary Search Explained with Java Solution (LeetCode 33)

Search in Rotated Sorted Array – Binary Search Explained with Java Solution (LeetCode 33)

Learn how to efficiently search for an element in a rotated sorted array using binary search. This guide explains the intuition, multiple strategies, and a clean Java implementation that achieves O(log n) time complexity.

14 views
0
0
Binary SearchJavaRotated Sorted ArrayLeetCodeMedium
Github icon

Try the Question

Before reading the solution, try solving the problem yourself:

👉 https://leetcode.com/problems/search-in-rotated-sorted-array/

Attempting the problem first helps build strong algorithmic intuition, which is extremely valuable during coding interviews.


Problem Statement

You are given an integer array nums that was originally sorted in ascending order with distinct elements.

Example of a sorted array:

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

Before the array is provided to the function, it may have been rotated at some pivot index k.

After rotation, the array structure becomes:

[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]

For example:

Original Array
[0,1,2,4,5,6,7]

Rotated by 3 positions
[4,5,6,7,0,1,2]

You are also given an integer target.

The goal is to return the index of the target element in the array.

If the element does not exist, return:

-1

Important Constraint

The algorithm must run in O(log n) time complexity, which strongly suggests using Binary Search.


Example Walkthrough

Example 1

Input

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

Output

4

Explanation:

0 exists at index 4

Example 2

Input

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

Output

-1

Explanation:

3 does not exist in the array

Example 3

Input

nums = [1]
target = 0

Output

-1


Understanding the Core Challenge

If the array were fully sorted, the problem would be straightforward because binary search could directly be applied.

Example:

[1,2,3,4,5,6,7]

However, due to rotation:

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

the array is no longer globally sorted.

But an important observation makes the problem solvable.

Key Observation

Even after rotation:

At least one half of the array is always sorted.

For example:

[4,5,6,7,0,1,2]
Left part → sorted
Right part → sorted

This property allows the use of binary search with additional conditions.


Approach 1 — Linear Scan (Brute Force)

The simplest method is to iterate through the entire array and check each element.

Algorithm

  1. Traverse the array from start to end.
  2. Compare every element with the target.
  3. Return the index if found.

Code

for(int i = 0; i < nums.length; i++){
if(nums[i] == target){
return i;
}
}
return -1;


Time Complexity

O(n)


Space Complexity

O(1)

Although simple, this solution does not satisfy the required O(log n) complexity.


Approach 2 — Modified Binary Search

A better solution uses binary search with sorted half detection.

Idea

At every step:

  1. Calculate the middle index.
  2. Determine which half of the array is sorted.
  3. Check if the target lies inside that sorted half.
  4. Adjust the search range accordingly.

Implementation

public int search(int[] nums, int target) {

int l = 0;
int r = nums.length - 1;

while(l <= r){

int mid = l + (r - l) / 2;

if(nums[mid] == target){
return mid;
}

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

if(nums[l] <= target && target < nums[mid]){
r = mid - 1;
}else{
l = mid + 1;
}
}

// right half sorted
else{

if(nums[mid] < target && target <= nums[r]){
l = mid + 1;
}else{
r = mid - 1;
}
}
}

return -1;
}


Time Complexity

O(log n)


Space Complexity

O(1)

This is the most common interview solution.


Approach 3 — Find Rotation Point Then Apply Binary Search

Another elegant strategy is to first locate the minimum element in the rotated array, which represents the rotation index (pivot).

Once the pivot is known, the array can be logically split into two sorted subarrays.

Example:

[4,5,6,7,0,1,2]
^
pivot

Two sorted sections exist:

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

After identifying the pivot:

  1. Decide which part may contain the target.
  2. Apply standard binary search on that portion.


Step 1 — Finding the Minimum Element (Rotation Pivot)

The smallest element indicates where the rotation happened.

Function to Find Minimum Value

public int findMinIndex(int[] nums){

int l = 0;
int r = nums.length - 1;

while(l < r){

int mid = l + (r - l) / 2;

if(nums[mid] > nums[r]){
l = mid + 1;
}else{
r = mid;
}
}

return l;
}


Why This Works

If:

nums[mid] > nums[r]

the minimum element must be on the right side.

Otherwise, it lies on the left side (including mid).


Step 2 — Standard Binary Search

After determining which half contains the target, a normal binary search is applied.

public int binarySearch(int[] nums, int l, int r, int target){

while(l <= r){

int mid = l + (r - l) / 2;

if(nums[mid] == target){
return mid;
}
else if(nums[mid] < target){
l = mid + 1;
}
else{
r = mid - 1;
}
}

return -1;
}


Complete Solution (Pivot + Binary Search)

class Solution {

public int findMinIndex(int[] nums){

int l = 0;
int r = nums.length - 1;

while(l < r){

int mid = l + (r - l) / 2;

if(nums[mid] > nums[r]){
l = mid + 1;
}else{
r = mid;
}
}

return l;
}

public int binarySearch(int[] nums, int l, int r, int target){

while(l <= r){

int mid = l + (r - l) / 2;

if(nums[mid] == target){
return mid;
}
else if(nums[mid] < target){
l = mid + 1;
}
else{
r = mid - 1;
}
}

return -1;
}

public int search(int[] nums, int target) {

int pivot = findMinIndex(nums);

if(nums[pivot] <= target && target <= nums[nums.length - 1]){
return binarySearch(nums, pivot, nums.length - 1, target);
}

return binarySearch(nums, 0, pivot - 1, target);
}
}


Time Complexity

Finding pivot:

O(log n)

Binary search:

O(log n)

Total complexity:

O(log n)


Space Complexity

O(1)

No additional memory is used.


Key Takeaways

✔ The array is sorted but rotated

✔ A rotation creates two sorted sections

✔ Binary search can still be applied

✔ Either detect the sorted half directly or locate the pivot first

✔ Both optimized approaches achieve O(log n) complexity


Final Thoughts

This problem is a classic binary search variation frequently asked in coding interviews. It evaluates the ability to:

  1. Recognize structural patterns in arrays
  2. Adapt binary search to non-standard conditions
  3. Maintain optimal algorithmic complexity

Understanding this pattern also helps solve related problems such as:

  1. Find Minimum in Rotated Sorted Array
  2. Search in Rotated Sorted Array II
  3. Find Rotation Count in Array

Mastering these concepts significantly strengthens binary search problem-solving skills for technical interviews.

Related Articles

Search in Rotated Sorted Array II – Binary Search with Duplicates Explained (LeetCode 81)

Search in Rotated Sorted Array II – Binary Search with Duplicates Explained (LeetCode 81)

Learn how to search an element in a rotated sorted array that may contain duplicate values. This guide explains the intuition, challenges caused by duplicates, and a clean Java solution using modified binary search.

Read Article
Find Peak Element – Binary Search Explained with Java Solution (LeetCode 162)

Find Peak Element – Binary Search Explained with Java Solution (LeetCode 162)

Learn how to efficiently find a peak element in an array using binary search. This guide explains the problem clearly, builds intuition step-by-step, and walks through multiple approaches with a clean O(log n) solution.

Read Article
Peak Index in a Mountain Array – Brute Force to Binary Search (LeetCode 852)

Peak Index in a Mountain Array – Brute Force to Binary Search (LeetCode 852)

Learn how to find the peak index in a mountain array using multiple approaches including brute force, linear scan, and an optimized binary search solution with O(log n) time complexity.

Read Article
Check if Binary String Has at Most One Segment of Ones – Java Solution (LeetCode 1784)

Check if Binary String Has at Most One Segment of Ones – Java Solution (LeetCode 1784)

Learn how to determine whether a binary string contains only one continuous group of 1s. This article explains the problem clearly, builds the intuition step-by-step, and walks through a clean Java solution with time complexity analysis.

Read Article

Ai Assistant Kas