Last updated on January 29th, 2025 at 02:27 am
Here, we see a Search in Rotated Sorted Array LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Array, Binary Search
Companies
Bloomberg, Facebook, Linkedin, Microsoft, Uber
Level of Question
Medium

Search in Rotated Sorted Array LeetCode Solution
Table of Contents
1. Problem Statement
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.
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].
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
2. Coding Pattern Used in Solution
The coding pattern used in all the provided implementations is Modified Binary Search. This pattern is a variation of the standard binary search algorithm, where the search space is adjusted based on specific conditions. In this case, the array is rotated, and the algorithm determines which part of the array to search based on the rotation and the target value.
3. Code Implementation in Different Languages
3.1 Search in Rotated Sorted Array C++
class Solution { public: int search(vector<int>& nums, int target) { int beg=0,end=nums.size()-1,mid; while(beg<=end) { mid=(beg+end)/2; if(nums[mid]==target) return mid; if(nums[beg]<=nums[mid]) { if(target<=nums[mid] && target>=nums[beg]) end=mid-1; else beg=mid+1; } else { if(target>=nums[mid] && target<=nums[end]) beg=mid+1; else end=mid-1; } } return -1; } };
3.2 Search in Rotated Sorted Array Java
class Solution { public int search(int[] nums, int target) { int lo = 0, hi = nums.length - 1; while (lo < hi) { int mid = (lo + hi) / 2; if ((nums[0] > target) ^ (nums[0] > nums[mid]) ^ (target > nums[mid])) lo = mid + 1; else hi = mid; } return lo == hi && nums[lo] == target ? lo : -1; } }
3.3 Search in Rotated Sorted Array JavaScript
var search = function(nums, target) { let start = 0, end = nums.length - 1; while(start<end){ let mid = Math.floor((start+end)/2); if(nums[mid]===target) return mid; if(nums[mid]>nums[start]){ if(target>=nums[start] && target<nums[mid]) end = mid-1; else start = mid+1; } else if(nums[mid]<nums[end]){ if(target>nums[mid] && target<=nums[end]) start = mid+1; else end = mid-1; } else break; } return nums[end]===target?end:-1; };
3.4 Search in Rotated Sorted Array Python
class Solution(object): def search(self, nums, target): lo, hi = 0, len(nums) - 1 while lo < hi: mid = (lo + hi) / 2 if (nums[0] > target) ^ (nums[0] > nums[mid]) ^ (target > nums[mid]): lo = mid + 1 else: hi = mid return lo if target in nums[lo:lo+1] else -1
4. Time and Space Complexity
Time Complexity | Space Complexity | |
C++ | O(log n) | O(1) |
Java | O(log n) | O(1) |
JavaScript | O(log n) | O(1) |
Python | O(log n) | O(1) |