Search in Rotated Sorted Array
Program for Searching in a Rotated Sorted Array Problem
You are given a sorted array that has been rotated between 1 and n times. For example:
If the array [1,2,3,4,5,6] is rotated 4 times, it becomes [3,4,5,6,1,2].
If rotated 6 times, it stays as [1,2,3,4,5,6].
Your task is to find the index of a given target number in this rotated array. If the target is not found, return -1.
You can assume that all elements in the array are unique.
While finding the target in O(n) time is straightforward, you need to design an algorithm that works in O(logn) time.
Example 1
Input: nums = [3,4,5,6,1,2], target = 1
Output: 4
Output: 4
Example 2
Input: nums = [3,5,6,0,1,2], target = 4
Output: -1
Output: -1
Constraints:
- 1 <= nums.length <= 1000
- -1000 <= nums[i] <= 1000
- -1000 <= target <= 1000
Program for Searching in a Rotated Sorted Array Solution
Recommendation for Time and Space Complexity – You should aim for a solution with O(logn) time and O(1) space, where n is the size of the input array.
Hints for solving problems
Hint 1 :
A brute force solution would be to do a linear search on the array to find the target element. This would be an O(n) solution. Can you think of a better way? Maybe an efficient searching algorithm is helpful.
Hint 2 :
A rotated sorted array forms two sorted segments separated by a pivot point. For example, [3,4,1,2] has two segments: [3,4] and [1,2]. To find a target efficiently, first locate the pivot using binary search, then perform binary search on the appropriate segment.
There are mainly 4 approach to solve this problem-
- Brute Force Method
- Binary Search Method
- Binary Search Method(Two Pass)
- Binary Search Method(One Pass)
1. Brute Force Method
Iterate through the entire array to find the target element, resulting in an O(n) solution.
- Time complexity: O(n)
- Space complexity: O(1)
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
int search(vector<int>& nums, int target) {
for (int i = 0; i < nums.size(); i++) {
if (nums[i] == target) {
return i;
}
}
return -1;
}
};
Java
class Solution {
public int search(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target) {
return i;
}
}
return -1;
}
}
Python
class Solution {
public:
int search(vector& nums, int target) {
for (int i = 0; i < nums.size(); i++) {
if (nums[i] == target) {
return i;
}
}
return -1;
}
};
JavaScript
class Solution {
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
search(nums, target) {
for (let i = 0; i < nums.length; i++) {
if (nums[i] == target) {
return i;
}
}
return -1;
}
}
2. Binary Search Method
Find the pivot point where the array is rotated, then perform binary search separately on the two sorted segments.
- Time complexity: O(log n)
- Space complexity: O(1)
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l < r) { int m = (l + r) / 2; if (nums[m] > nums[r]) {
l = m + 1;
} else {
r = m;
}
}
int pivot = l;
int result = binarySearch(nums, target, 0, pivot - 1);
if (result != -1) {
return result;
}
return binarySearch(nums, target, pivot, nums.size() - 1);
}
int binarySearch(vector& nums, int target, int left, int right) {
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
};
Java
public class Solution {
public int search(int[] nums, int target) {
int l = 0, r = nums.length - 1;
while (l < r) {
int m = (l + r) / 2;
if (nums[m] > nums[r]) {
l = m + 1;
} else {
r = m;
}
}
int pivot = l;
int result = binarySearch(nums, target, 0, pivot - 1);
if (result != -1) {
return result;
}
return binarySearch(nums, target, pivot, nums.length - 1);
}
public int binarySearch(int[] nums, int target, int left, int right) {
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
}
Python
class Solution:
def search(self, nums: List[int], target: int) -> int:
l, r = 0, len(nums) - 1
while l < r:
m = (l + r) // 2
if nums[m] > nums[r]:
l = m + 1
else:
r = m
pivot = l
def binary_search(left: int, right: int) -> int:
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
result = binary_search(0, pivot - 1)
if result != -1:
return result
return binary_search(pivot, len(nums) - 1)
JavaScript
class Solution {
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
search(nums, target) {
let l = 0;
let r = nums.length - 1;
while (l < r) {
const m = Math.floor((l + r) / 2);
if (nums[m] > nums[r]) {
l = m + 1;
} else {
r = m;
}
}
const pivot = l;
const result = this.binarySearch(nums, target, 0, pivot - 1);
if (result !== -1) {
return result;
}
return this.binarySearch(nums, target, pivot, nums.length - 1);
}
/**
* @param {number[]} nums
* @param {number} target
* @param {number} left
* @param {number} right
* @return {number}
*/
binarySearch(nums, target, left, right) {
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;
}
}
3. Binary Search Method(Two Pass)
First, locate the pivot using binary search, then conduct a second binary search in the appropriate half to find the target.
- Time complexity: O(log n)
- Space complexity: O(1)
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l < r) { int m = (l + r) / 2; if (nums[m] > nums[r]) {
l = m + 1;
} else {
r = m;
}
}
int pivot = l;
l = 0;
r = nums.size() - 1;
if (target >= nums[pivot] && target <= nums[r]) {
l = pivot;
} else {
r = pivot - 1;
}
while (l <= r) {
int m = (l + r) / 2;
if (nums[m] == target) {
return m;
} else if (nums[m] < target) {
l = m + 1;
} else {
r = m - 1;
}
}
return -1;
}
};
Java
public class Solution {
public int search(int[] nums, int target) {
int l = 0, r = nums.length - 1;
while (l < r) {
int m = (l + r) / 2;
if (nums[m] > nums[r]) {
l = m + 1;
} else {
r = m;
}
}
int pivot = l;
l = 0;
r = nums.length - 1;
if (target >= nums[pivot] && target <= nums[r]) {
l = pivot;
} else {
r = pivot - 1;
}
while (l <= r) {
int m = (l + r) / 2;
if (nums[m] == target) {
return m;
} else if (nums[m] < target) {
l = m + 1;
} else {
r = m - 1;
}
}
return -1;
}
}
Python
class Solution:
def search(self, nums: List[int], target: int) -> int:
l, r = 0, len(nums) - 1
while l < r:
m = (l + r) // 2
if nums[m] > nums[r]:
l = m + 1
else:
r = m
pivot = l
l, r = 0, len(nums) - 1
if target >= nums[pivot] and target <= nums[r]:
l = pivot
else:
r = pivot - 1
while l <= r:
m = (l + r) // 2
if nums[m] == target:
return m
elif nums[m] < target:
l = m + 1
else:
r = m - 1
return -1
JavaScript
class Solution {
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
search(nums, target) {
let l = 0, r = nums.length - 1;
while (l < r) {
let m = Math.floor((l + r) / 2);
if (nums[m] > nums[r]) {
l = m + 1;
} else {
r = m;
}
}
let pivot = l;
l = 0;
r = nums.length - 1;
if (target >= nums[pivot] && target <= nums[r]) {
l = pivot;
} else {
r = pivot - 1;
}
while (l <= r) {
let m = Math.floor((l + r) / 2);
if (nums[m] === target) {
return m;
} else if (nums[m] < target) {
l = m + 1;
} else {
r = m - 1;
}
}
return -1;
}
}
4. Binary Search Method(One Pass)
Modify binary search logic to account for the rotation, adjusting search conditions dynamically to find the target in a single pass.
- Time complexity: O(log n)
- Space complexity: O(1)
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
int search(std::vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (target == nums[mid]) {
return mid;
}
if (nums[l] <= nums[mid]) { if (target > nums[mid] || target < nums[l]) {
l = mid + 1;
} else {
r = mid - 1;
}
} else {
if (target < nums[mid] || target > nums[r]) {
r = mid - 1;
} else {
l = mid + 1;
}
}
}
return -1;
}
};
Java
class Solution {
public int search(int[] nums, int target) {
int l = 0;
int r = nums.length - 1;
while(l <= r) {
int mid = (l + r) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[l] <= nums[mid]) {
if (target > nums[mid] || target < nums[l]) {
l = mid + 1;
} else {
r = mid - 1;
}
} else {
if (target < nums[mid] || target > nums [r]) {
r = mid - 1;
} else {
l = mid + 1;
}
}
}
return -1;
}
}
Python
class Solution:
def search(self, nums: List[int], target: int) -> int:
l, r = 0, len(nums) - 1
while l <= r:
mid = (l + r) // 2
if target == nums[mid]:
return mid
if nums[l] <= nums[mid]:
if target > nums[mid] or target < nums[l]:
l = mid + 1
else:
r = mid - 1
else:
if target < nums[mid] or target > nums[r]:
r = mid - 1
else:
l = mid + 1
return -1
JavaScript
class Solution {
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
search(nums, target) {
let l = 0, r = nums.length - 1;
while (l <= r) {
const mid = Math.floor((l + r) / 2);
if (target === nums[mid]) {
return mid;
}
if (nums[l] <= nums[mid]) {
if (target > nums[mid] || target < nums[l]) {
l = mid + 1;
} else {
r = mid - 1;
}
} else {
if (target < nums[mid] || target > nums[r]) {
r = mid - 1;
} else {
l = mid + 1;
}
}
}
return -1;
}
}
