Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Search in Rotated Sorted Array solution and explanation

MediumArrayBinary Search6 min read45.5% acceptanceUpdated 9 Apr 2026
Asked atLinkedInAutodeskDelhiveryWishF5 NetworksGoto
+14 moreNewsbreakGainsightSixtWalmart LabsGrammarlyTinkoffDP WorldCriteoCohesityAmazonMicrosoftBloombergTiktokNVIDIA
Practise Search in Rotated Sorted Array
13:28
Search in rotated sorted array - Leetcode 33 - PythonNeetCode · 13:28 · 543K viewsWatch on YouTube
9 more videos on this problem
  1. Search in rotated sorted array - Leetcode 33 - PythonNeetCode · 13:28 · 543K views
  2. Search in Rotated Sorted Array | Binary Search | Leetcode 33Apna College · 19:30 · 295K views
  3. LeetCode 33. Search in Rotated Sorted ArrayNick White · 9:30 · 103K views
  4. Search in rotated sorted array | Leetcode #33Techdose · 13:52 · 86K views
  5. Search in a Rotated Sorted Array (LeetCode 33) | Full solution with examples | Study AlgorithmsNikhil Lohia · 14:51 · 40K views
  6. Search in Rotated Sorted Array - Leetcode 33 - Binary Search (Python)Greg Hogg · 9:07 · 25K views
  7. Search in Rotated Sorted Array | LeetCode problem 33Technosage · 11:35 · 11K views
  8. Search In Rotated Sorted Array - LeetCode 33 - Binary SearchOne Code Man · 5:21 · 5K views
  9. Search in Rotated Sorted Array - LeetCode 33 - JavaScriptAlgoJS · 6:13 · 2K views
  10. Leetcode 33. Search in Rotated Sorted Array (Python)Pseudocoder Ravina · 15:19 · 1K views

The problem

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

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

Constraints:

  • 1 <= nums.length <= 5000
  • -104 <= nums[i] <= 104
  • All values of nums are unique.
  • nums is an ascending array that is possibly rotated.
  • -104 <= target <= 104

Approach overview

Problem Overview: You get a sorted array that has been rotated at an unknown pivot. The order is still increasing on each side of the pivot. Your task is to find the index of a target value in O(log n) time. If the target does not exist, return -1.

Approach 1: Linear Scan (O(n) time, O(1) space)

The simplest approach is to iterate through the array and compare each element with the target. The moment you find a match, return its index. If the loop finishes without a match, return -1. This ignores the sorted property entirely and works for any array. While easy to implement, it runs in O(n) time, which fails the logarithmic time expectation usually implied in interview settings.

Approach 2: Binary Search with Rotation Logic (O(log n) time, O(1) space)

This approach modifies standard binary search. Even though the array is rotated, at least one half of the array remains sorted at any moment. Compute mid. If nums[mid] equals the target, return it immediately. Otherwise check whether the left half (nums[left]..nums[mid]) is sorted. If it is, verify whether the target lies inside that range and adjust right. If not, move left to the other half. If the right half is sorted, perform the symmetric check. This keeps halving the search space while respecting the rotation property.

Approach 3: Find Rotation Index then Binary Search (O(log n) time, O(1) space)

This method separates the problem into two steps. First, locate the rotation pivot using binary search. The pivot is the smallest element where the order breaks. Once you know the pivot, the array effectively becomes two sorted segments. Decide which segment could contain the target by comparing it with boundary values, then run a normal binary search on that half. This approach explicitly identifies the rotation structure, which some developers find easier to reason about when working with array transformations.

Recommended for interviews: The modified binary search with rotation logic is the expected solution. It keeps the implementation compact while maintaining O(log n) time. Explaining the linear scan briefly shows baseline reasoning, but demonstrating the rotated binary search proves you understand how sorted structure enables logarithmic search.

Approach 1: Binary Search with Rotation Logic

The essence of this approach is to perform a binary search with a twist, considering the rotation. We first determine which part of the array is sorted: the left or the right. This allows us to intelligently decide where to perform the binary search. If the target lies within the sorted side, we adjust the search range accordingly. Otherwise, we continue the search on the unsorted side, which in the next iteration becomes a new array.

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            if nums[left] <= nums[mid]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
        return -1
class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;
            if (nums[left] <= nums[mid]) {
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
}
#include <vector>
class Solution {
public:
    int search(std::vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;
            if (nums[left] <= nums[mid]) {
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
};
var search = function(nums, target) {
    let left = 0, right = nums.length - 1;
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (nums[mid] === target) return mid;
        if (nums[left] <= nums[mid]) {
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    return -1;
};
#include <stdio.h>
int search(int* nums, int numsSize, int target) {
    int left = 0, right = numsSize - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;
        if (nums[left] <= nums[mid]) {
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    return -1;
}
public class Solution {
    public int Search(int[] nums, int target) {
        int left = 0, right = nums.Length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;
            if (nums[left] <= nums[mid]) {
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
}

This method explores the nature of the rotated array through a binary search. The search region narrows depending on adjusted mid-index scope, focusing on the sorted half unless the target's location points to the opposite half.

Complexity

Time Complexity: O(log n) inherent in binary search efficiency.
Space Complexity: O(1), permitting only minimal additional space usage.

Try this approach in the editor

Approach 2: Find Rotated Index and Execute Two Binary Searches

This decomposition-based approach first identifies the pivot index where rotation occurs. Once the break index is acquired, the target search bifurcates: running binary search on subarrays from the determined split point to either the beginning or end of the array.

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        pivot = self.findPivot(nums)
        if nums[pivot] <= target <= nums[-1]:
            return self.binarySearch(nums, pivot, len(nums) - 1, target)
        else:
            return self.binarySearch(nums, 0, pivot - 1, target)

    def findPivot(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] > nums[right]:
                left = mid + 1
            else:
                right = mid
        return left

    def binarySearch(self, nums: List[int], left: int, right: int, target: int) -> int:
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return -1
class Solution {
    public int search(int[] nums, int target) {
        if (nums.length == 0) return -1;
        int pivot = findPivot(nums);
        if (nums[pivot] <= target && target <= nums[nums.length - 1]) 
            return binarySearch(nums, pivot, nums.length - 1, target);
        else 
            return binarySearch(nums, 0, pivot - 1, target);
    }

    private int findPivot(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right])
                left = mid + 1;
            else
                right = mid;
        }
        return left;
    }

    private int binarySearch(int[] nums, int left, int right, int target) {
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;
            else if (nums[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    }
}
#include <vector>
class Solution {
public:
    int findPivot(const std::vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right])
                left = mid + 1;
            else
                right = mid;
        }
        return left;
    }
    
    int binarySearch(const std::vector<int>& nums, int left, int right, int target) {
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;
            else if (nums[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    }

    int search(std::vector<int>& nums, int target) {
        if (nums.empty()) return -1;
        int pivot = findPivot(nums);
        if (nums[pivot] <= target && target <= nums.back()) 
            return binarySearch(nums, pivot, nums.size() - 1, target);
        else 
            return binarySearch(nums, 0, pivot - 1, target);
    }
};
var search = function(nums, target) {
    if (nums.length === 0) return -1;
    const pivot = findPivot(nums);
    if (nums[pivot] <= target && target <= nums[nums.length - 1]) {
        return binarySearch(nums, pivot, nums.length - 1, target);
    } else {
        return binarySearch(nums, 0, pivot - 1, target);
    }
};

function findPivot(nums) {
    let left = 0, right = nums.length - 1;
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (nums[mid] > nums[right]) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

function binarySearch(nums, left, right, target) {
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (nums[mid] === target) return mid;
        else if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}
#include <stdio.h>
int findPivot(int* nums, int numsSize) {
    int left = 0, right = numsSize - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] > nums[right])
            left = mid + 1;
        else
            right = mid;
    }
    return left;
}

int binarySearch(int* nums, int left, int right, int target) {
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

int search(int* nums, int numsSize, int target) {
    if (numsSize == 0) return -1;
    int pivot = findPivot(nums, numsSize);
    if (nums[pivot] <= target && target <= nums[numsSize - 1]) 
        return binarySearch(nums, pivot, numsSize - 1, target);
    else 
        return binarySearch(nums, 0, pivot - 1, target);
}
public class Solution {
    public int Search(int[] nums, int target) {
        if (nums.Length == 0) return -1;
        int pivot = FindPivot(nums);
        if (nums[pivot] <= target && target <= nums[nums.Length - 1])
            return BinarySearch(nums, pivot, nums.Length - 1, target);
        else
            return BinarySearch(nums, 0, pivot - 1, target);
    }

    private int FindPivot(int[] nums) {
        int left = 0, right = nums.Length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right])
                left = mid + 1;
            else
                right = mid;
        }
        return left;
    }

    private int BinarySearch(int[] nums, int left, int right, int target) {
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;
            else if (nums[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    }
}

This procedural solution delineates the task into finding the potential rotation point and subsequently dividing the search task using standard binary logic, applied separately to distinct parts of the array based on observed rotations.

Complexity

Time Complexity: O(log n) including both pivot-identification and dual-binary computations.
Space Complexity: O(1), highlighting a focus on in-place calculations barring recursion depth.

Try this approach in the editor

Approach 3: Binary Search

We use binary search to divide the array into two parts, [left,.. mid] and [mid + 1,.. right]. At this point, we can find that one part must be sorted.

Therefore, we can determine whether target is in this part based on the sorted part:

  • If the elements in the range [0,.. mid] form a sorted array:
    • If nums[0] leq target leq nums[mid], then our search range can be narrowed down to [left,.. mid];
    • Otherwise, search in [mid + 1,.. right];
  • If the elements in the range [mid + 1, n - 1] form a sorted array:
    • If nums[mid] \lt target leq nums[n - 1], then our search range can be narrowed down to [mid + 1,.. right];
    • Otherwise, search in [left,.. mid].

The termination condition for binary search is left geq right. If at the end we find that nums[left] is not equal to target, it means that there is no element with a value of target in the array, and we return -1. Otherwise, we return the index left.

The time complexity is O(log n), where n is the length of the array nums. The space complexity is O(1).

function search(nums: number[], target: number): number {
    const n = nums.length;
    let left = 0,
        right = n - 1;
    while (left < right) {
        const mid = (left + right) >> 1;
        if (nums[0] <= nums[mid]) {
            if (nums[0] <= target && target <= nums[mid]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        } else {
            if (nums[mid] < target && target <= nums[n - 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
    }
    return nums[left] == target ? left : -1;
}
func search(nums []int, target int) int {
	n := len(nums)
	left, right := 0, n-1
	for left < right {
		mid := (left + right) >> 1
		if nums[0] <= nums[mid] {
			if nums[0] <= target && target <= nums[mid] {
				right = mid
			} else {
				left = mid + 1
			}
		} else {
			if nums[mid] < target && target <= nums[n-1] {
				left = mid + 1
			} else {
				right = mid
			}
		}
	}
	if nums[left] == target {
		return left
	}
	return -1
}
impl Solution {
    pub fn search(nums: Vec<i32>, target: i32) -> i32 {
        let mut l = 0;
        let mut r = nums.len() - 1;
        while l <= r {
            let mid = (l + r) >> 1;
            if nums[mid] == target {
                return mid as i32;
            }

            if nums[l] <= nums[mid] {
                if target < nums[mid] && target >= nums[l] {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {
                if target > nums[mid] && target <= nums[r] {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        -1
    }
}
class Solution {
    /**
     * @param integer[] $nums
     * @param integer $target
     * @return integer
     */

    function search($nums, $target) {
        $foundKey = -1;
        foreach ($nums as $key => $value) {
            if ($value === $target) {
                $foundKey = $key;
            }
        }
        return $foundKey;
    }
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Binary Search with Rotation Logic

Time Complexity: O(log n) inherent in binary search efficiency.
Space Complexity: O(1), permitting only minimal additional space usage.

Find Rotated Index and Execute Two Binary Searches

Time Complexity: O(log n) including both pivot-identification and dual-binary computations.
Space Complexity: O(1), highlighting a focus on in-place calculations barring recursion depth.

Binary Search–

Complexity analysis

ApproachTimeSpaceWhen to Use
Linear ScanO(n)O(1)Quick brute-force check or when input size is very small
Binary Search with Rotation LogicO(log n)O(1)General optimal solution expected in coding interviews
Find Pivot then Binary SearchO(log n)O(1)Useful when you want a clear pivot-based reasoning for rotated arrays

Frequently asked questions

Is Search in Rotated Sorted Array easy or hard?

The problem is typically classified as Medium. Basic binary search knowledge is required, but the rotation condition adds a reasoning step where you must determine which side of the array remains sorted before deciding where to search.

Search in Rotated Sorted Array Python/Java solution

Python and Java implementations follow the same pattern: maintain left and right pointers, compute mid, detect the sorted half, and move the pointers accordingly. The logic runs in O(log n) time and uses constant extra space.

How to solve Search in Rotated Sorted Array in O(log n)?

Use binary search but first determine which half of the array is sorted. Compare nums[left], nums[mid], and nums[right] to detect the sorted segment. If the target falls within that segment, continue searching there; otherwise search the other half. This preserves logarithmic time complexity.

What is the best approach for Search in Rotated Sorted Array?

The best approach uses modified binary search that detects which half of the array is sorted during each iteration. By checking whether the target lies inside the sorted half, you can discard half of the search space every step. This keeps the runtime at O(log n) with O(1) extra space.

Is Search in Rotated Sorted Array asked at Google/Amazon/Meta?

Search in Rotated Sorted Array frequently appears in technical interviews at companies like Amazon, Google, and Meta. Interviewers use it to test binary search variations and reasoning about partially sorted arrays.

What data structure is used in Search in Rotated Sorted Array?

The problem operates directly on an array and relies on binary search logic. No additional data structures are required because the algorithm only tracks indices such as left, mid, and right while narrowing the search range.

What is the time complexity of Search in Rotated Sorted Array?

The optimal solution runs in O(log n) time because it applies binary search while handling the rotation condition. Each iteration cuts the search space in half. Space complexity stays O(1) since the algorithm uses only a few pointers.

Comments

Next problem · similarSearch in Rotated Sorted Array IIMedium
Now write it yourselfClose this page and solve Search in Rotated Sorted Array in the editor, without looking.
Practise Search in Rotated Sorted Array