Search in rotated sorted array leetcode solution | Code In C++/Python/Java
Problem Description:
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.
Examples:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Explanation: We can see that the occurrence of 0 in nums is at index 4, so return 4.
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
Explanation: We can see that there is no occurrence of 3 in nums, so return -1.
Input: nums = [1], target = 0
Output: -1
Explanation: There is no occurrence of 0 in nums, so return -1.
Constraints:
- 1 <= nums.length <= 5000
- -10⁴ <= nums[i] <= 10⁴
- All values of nums are unique.
- nums is an ascending array that is possibly rotated.
- -10⁴ <= target <= 10⁴
For now, forget that array is rotated and sorted. Reduce the problem statement to find the index of the target in the array.
How would you approach this problem? Let's discuss
Brute Force Approach
Intuition:
We are supposed to return the index with the value target. The first thought that arises is why not check every index and see if its value is equal to the target.
Search in rotated sorted array leetcode solution.
You start at the beginning of the array and compare each element with the target value. If you find an element that matches the target, you return the position (index) of that element. If the element doesn't match, you move to the next one and continue this process until you find the target or reach the end of the array. If you get to the end of the array without finding the target value, you return -1 to indicate that the target is not present in the array. This method ensures that you check every possible position in the array to find the target value.
Dry run
Input: nums = [9, 11, 1, 5, 7], target = 5
Output: 3
Initialization:
- nums = [9, 11, 1, 5, 7]
- target = 5
- n = nums.size() = 5
Iteration through the array:
- First iteration (i = 0):
- nums[0] = 9
- Check if(nums[0] == target): if(9 == 5): false
- Continue to the next iteration.
- Second iteration (i = 1):
- nums[1] = 11
- Check if(nums[1] == target): if(11 == 5): false
- Continue to the next iteration.
- Third iteration (i = 2):
- nums[2] = 1
- Check if(nums[2] == target): if(1 == 5): false
- Continue to the next iteration.
- Fourth iteration (i = 3):
- nums[3] = 5
- Check if(nums[3] == target): if(5 == 5): true
- Target found, return 3.
Result:
- The function returns 3, which is the index of the target 5 in the array nums.
Steps to write code
Step 1: Get the Size of the Array:
- Determine the size of the array using nums.size() and store it in a variable n.
Step 2: Iterate Through the Array:
- Use a for loop to iterate through each element in the array. The loop variable i will range from 0 to n-1.
Step 3: Check Each Element:
- Inside the loop, check if the current element (nums[i]) is equal to the target. If it is, return the index i.
Step 4: Return -1 if Target Not Found:
- If the loop completes without finding the target, return -1 to indicate that the target is not present in the array.
Brute Force in All Languages
C++
class Solution {
public:
// Function to search for the target in the array
int search(vector<int>& nums, int target) {
int n = nums.size(); // Get the size of the array
// Iterate through the array
for (int i = 0; i < n; ++i) {
// Check if the current element is the target
if (nums[i] == target) {
return i; // Return the index if target is found
}
}
return -1; // Return -1 if target is not found
}
};Java
class Solution {
// Function to search for the target in the array
public int search(int[] nums, int target) {
// Get the size of the array
int n = nums.length;
// Iterate through the array
for (int i = 0; i < n; ++i) {
// Check if the current element is the target
if (nums[i] == target) {
// Return the index if target is found
return i;
}
}
// Return -1 if target is not found
return -1;
}
}Python
class Solution:
def search(self, nums: list[int], target: int) -> int:
# Get the size of the array
n = len(nums)
# Iterate through the array
for i in range(n):
# Check if the current element is the target
if nums[i] == target:
# Return the index if target is found
return i
# Return -1 if target is not found
return -1Javascript
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var search = function(nums, target) {
// Get the size of the array
let n = nums.length;
// Iterate through the array
for (let i = 0; i < n; ++i) {
// Check if the current element is the target
if (nums[i] === target) {
// Return the index if target is found
return i;
}
}
// Return -1 if target is not found
return -1;
}Complexity Analysis of Search in rotated sorted array leetcode solution
Time Complexity: O(n)
Initialization
- The size of the array is determined using nums.size(), which takes O(1) time.
Loop Execution
- A for loop iterates through all n elements in the array. which takes O(n) time at worst case.
Condition Check
- In each iteration, the current element is compared with the target, which takes O(1) time.
Return Statement
- If the target is not found, -1 is returned, which takes O(1) time
Hence the overall time complexity is O(n).
Space Complexity: O(1)
Auxiliary Space Complexity:
- The algorithm does not use any additional data structures (like arrays, lists, or maps) that grow with the input size.
- The only extra space used is for a few integer variables (n and i), which take constant space.
- The Auxiliary Space Complexity is O(1)
Total Space Complexity:
- The total space complexity includes the space taken by the input array and any additional space used by the algorithm.
- Since the input array nums is provided as an argument, its space is considered part of the input.
- The input array nums takes O(n) space, where n is the size of the array.
- The Total Space Complexity is O(n)
Is the brute force approach efficient?
The time complexity of brute force is O(n). n goes up to 5000. In one second system can perform 107 operations. This means that the solution will easily pass. But in the problem, we neglected two things.
- The array is sorted and rotated.
- The solution must have O(logn) complexity.
Let's now address these points and optimize our solution.
Optimal Approach
Intuition:
Now, before directly going towards the solution, I would highly recommend looking at the following, which aims to find the minimum value index in the sorted rotated array.
Now, to reduce the complexity to O(logn). We can't afford to traverse the whole array instead, we need to strategically select the part of the array where we know we will find our target.
Provided that the array is sorted and rotated,,,d we can make a critical observation here. The rotation divides the array into two halves. One half ranges from index 0 to the index of the pivot - 1, and the other half ranges from the index of the pivot to the end (n-1).
The pivot point is where the smallest element (minimum) resides. This point effectively splits the array into two subarrays: the first half (from the original start to just before the pivot) and the second half (from the pivot to the original end of the array).
Let's say we pick a random position, which we'll call index i, from the array. This position will either be in the first part or the second part of the array. Additionally, we know that every number in the first part of the array is larger than every number in the second part of the array. If you are finding it hard to deduce this, please read the article given above for the problem "find minimum in sorted rotated array".
Using this information, we can figure out if our chosen position is in the first part or the second part. To do this, we simply need to compare the number at index 0(the very first number in the array) with the number at our chosen index i. If the number at index 0 is smaller than the number at our chosen index, then our chosen index is in the first half. Otherwise, it's in the second half.
Now that we know which half of the array our chosen index i lies in, let's take a closer look at it.
Case 1: Index i lies in the First Half
In this case, we can be certain that all the values from the start of the array (index 0) up to our chosen index i are sorted in ascending order. This knowledge is crucial because it helps us determine where to search next.
Here's how we can use this information:
- Check If the Target Is on the Left side of index i:
Since we know the values from index 0 to index i are sorted, we can check if the target value lies within this range. To do this, we compare the target value with the values at index 0 and index i.
If the target value is greater than or equal to the value at index 0 and less than or equal to the value at index i, then the target must be somewhere between these two indices.
In this case, we continue our search in the left half of the array, from index 0 to index i.
- Check If the Target Is on the Right side of index i:
If the target value is not within the range of index 0 to index i, it means the target is not in the left half.
Therefore, we should focus our search on the right half of the array, from index i+1 to the end of the array.
This is because we have already determined that the target is not in the left half, so it must be in the right half if it exists in the array.
Example:
Let's say we have an array [10, 20, 30, 40, 50, 5, 6, 7], and our target value is 30. We choose index i = 3 (value 40):
We know index 3 is in the first half because all values from index 0 to index 3 are sorted. We compare the target value 30 with the values at index 0 (10) and index 3 (40). Since 30 lies between 10 and 40, we know the target is in the left half. Therefore, we continue our search from index 0 to index 3.
If our target value was 6 instead:
Again, index 3 is in the first half. We compare the target value 6 with the values at index 0 (10) and index 3 (40). Since 6 is not between 10 and 40, we look at the right half. Thus, we continue our search from index 4 to the end of the array.
Case 2: Index i lies in the Second Half
In this case, we know that our chosen index i is in the second part of the array. All the values from the index i to the end of the array are sorted in ascending order. This information is crucial because it helps us determine where to search next.
Here's how we can use this information:
- Check If the Target Is on the Right Side of Index i:
Since we know the values from index i to the end of the array are sorted, we can check if the target value lies within this range. To do this, we compare the target value with the values at index i and the last index of the array.
If the target value is greater than or equal to the value at index i and less than or equal to the value at the last index, then the target must be somewhere between these two indices.
In this case, we continue our search in the right half of the array, from index i to the last index.
- Check If the Target Is on the Left Side of Index i:
If the target value is not within the range of index i to the last index, it means the target is not in the right half.
Therefore, we should focus our search on the left half of the array, from the start of the array (index 0) to index i-1.
This is because we have already determined that the target is not in the right half, so it must be in the left half if it exists in the array.
Example:
Let's say we have an array [50, 60, 70, 80, 10, 20, 30, 40], and our target value is 30. We choose index i = 5 (value 20):
We know index 5 is in the second half because all values from index 5 to the end of the array are sorted. We compare the target value 30 with the values at index 5 (20) and the last index 7 (40). Since 30 lies between 20 and 40, we know the target is in the right half. Therefore, we continue our search from index 5 to the last index 7.
If our target value was 60 instead:
Again, index 5 is in the second half. We compare the target value 60 with the values at index 5 (20) and the last index 7 (40).
- Since 60 is not between 20 and 40, we look at the left half.
- Thus, we continue our search from index 0 to index 4.
By following these steps, we can efficiently narrow down our search space and find our target.
Search in Rotated Sorted Array Algorithm
We first define our search space using two pointers,, which initially lie at the two ends of the array. Namely l (low) and h (high). All the decisions are made using the values at indexes l, arbitrary index i and h.
Until now, we learned for l=0 and h=n-1. When we finally decide which side the target is, then we update l or h concerning index i. We then repeat the same process for the new search space defined by updated low or high
For efficiency, the arbitrary index we were talking about choosing is the middle index of the array, as it will help to halve our search space at every iteration, ensuring maximum efficiency.
With appropriate comparisons and verifying which case the middle index satisfies, we narrow down our search space to one-half of the area,y neglecting the other half. Making things efficient.
This process of continuously narrowing down the search space and eventually finding the answer is called binary search.
To know more about binary search, refer to the article below...
Animation for Optimal Approach of Search in Rotated Sorted Array
Dry run
Input: nums = [9, 11, 1, 5, 7], target = 5
Output: 3
Initialization:
- nums = [9, 11, 1, 5, 7]
- target = 5
- n = arr.size() = 5
- l = 0
- h = n - 1 = 4
First Iteration:
- Calculate mid: mid = l + (h - l) / 2 = 0 + (4 - 0) / 2 = 2
- Check if (nums[mid] == target): if (nums[2] == 5): `if (1 == 5): false
- Check else if (nums[l] <= nums[mid]): else if (nums[0] <= nums[2]): else if (9 <= 1): false
- Else (right half sorted):
- Check if (nums[mid] < target && target <= nums[h]): if (1 < 5 && 5 <= 7): true
- Update l = mid + 1 = 2 + 1 = 3
Second Iteration:
- Calculate mid: mid = l + (h - l) / 2 = 3 + (4 - 3) / 2 = 3
- Check if (nums[mid] == target): if (nums[3] == 5): if (5 == 5): true
- Target found, return mid = 3
Result:
- The function returns 3, which is the index of the target 5 in the array nums.
Steps to write code
Step 1: Initialize Pointers:
- Initialize two pointers, l (left) set to 0 and h (right) set to the last index of the array (n-1), where n is the size of the array.
Step 2: Binary Search Loop:
- Use a while loop to perform the binary search as long as l is less than or equal to h.
Step 3: Calculate Middle Index:
- Calculate the middle index mid using the formula: mid = l + (h - l) / 2.
Step 4: Check if Target is at Middle:
- If the value at the mid index is equal to the target, return the mid index.
Step 5: Determine Sorted Half:
- If the left half (nums[l] to nums[mid]) is sorted:
- Check if the target lies within this sorted half.
- If yes, adjust the right pointer h to mid - 1.
- If no, adjust the left pointer l to mid + 1.
- If the right half (nums[mid] to nums[h]) is sorted:
- Check if the target lies within this sorted half.
- If yes, adjust the left pointer l to mid + 1.
- If no, adjust the right pointer h to mid - 1.
Step 6: Return -1 if Target Not Found:
- If the loop completes without finding the target, return -1 to indicate that the target is not present in the array.
Optimal Approach in All Languages
Search in rotated sorted array solution code in C++
class Solution {
public:
// Function to search for the target in the rotated sorted array
int search(vector<int>& nums, int target) {
// Get the size of the array
int n = nums.size();
// Initialize pointers
int l = 0, h = n - 1;
// Perform binary search
while (l <= h) {
// Calculate the middle index
int mid = l + (h - l) / 2;
// Check if the target is at the middle index
if (nums[mid] == target) {
return mid;
}
// Check if the left half is sorted
else if (nums[l] <= nums[mid]) {
// Check if the target is in the left half
if (nums[l] <= target && target < nums[mid]) {
h = mid - 1;
} else {
l = mid + 1;
}
}
// Right half is sorted
else {
// Check if the target is in the right half
if (nums[mid] < target && target <= nums[h]) {
l = mid + 1;
} else {
h = mid - 1;
}
}
}
// Return -1 if target is not found
return -1;
}
};Search in rotated sorted array solution code in Java
class Solution {
// Function to search for the target in the rotated sorted array
public int search(int[] nums, int target) {
// Get the size of the array
int n = nums.length;
// Initialize pointers
int l = 0, h = n - 1;
// Perform binary search
while (l <= h) {
// Calculate the middle index
int mid = l + (h - l) / 2;
// Check if the target is at the middle index
if (nums[mid] == target) {
return mid;
}
// Check if the left half is sorted
else if (nums[l] <= nums[mid]) {
// Check if the target is in the left half
if (nums[l] <= target && target < nums[mid]) {
h = mid - 1;
} else {
l = mid + 1;
}
}
// Right half is sorted
else {
// Check if the target is in the right half
if (nums[mid] < target && target <= nums[h]) {
l = mid + 1;
} else {
h = mid - 1;
}
}
}
// Return -1 if target is not found
return -1;
}
}Search in rotated sorted array solution code in Python
class Solution:
def search(self, nums: list[int], target: int) -> int:
# Get the size of the array
n = len(nums)
# Initialize pointers
l, h = 0, n - 1
# Perform binary search
while l <= h:
# Calculate the middle index
mid = l + (h - l) // 2
# Check if the target is at the middle index
if nums[mid] == target:
return mid
# Check if the left half is sorted
elif nums[l] <= nums[mid]:
# Check if the target is in the left half
if nums[l] <= target < nums[mid]:
h = mid - 1
else:
l = mid + 1
# Right half is sorted
else:
# Check if the target is in the right half
if nums[mid] < target <= nums[h]:
l = mid + 1
else:
h = mid - 1
# Return -1 if target is not found
return -1Search in rotated sorted array solution code in Javascript
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var search = function(nums, target) {
// Get the size of the array
let n = nums.length;
// Initialize pointers
let l = 0, h = n - 1;
// Perform binary search
while (l <= h) {
// Calculate the middle index
let mid = l + Math.floor((h - l) / 2);
// Check if the target is at the middle index
if (nums[mid] === target) {
return mid;
}
// Check if the left half is sorted
else if (nums[l] <= nums[mid]) {
// Check if the target is in the left half
if (nums[l] <= target && target < nums[mid]) {
h = mid - 1;
} else {
l = mid + 1;
}
}
// Right half is sorted
else {
// Check if the target is in the right half
if (nums[mid] < target && target <= nums[h]) {
l = mid + 1;
} else {
h = mid - 1;
}
}
}
// Return -1 if target is not found
return -1;
}
Complexity Analysis of Search in Rotated Sorted Array Solution
Time Complexity:
Initialization:
- n = nums.size(): This operation takes O(1) time because it simply calculates the size of the array.
- l = 0, h = n - 1 : These initializations take constant time O(1).
Binary Search Loop:
- In each iteration, the search space is halved by adjusting either the l (low) or h (high) pointers.
- The loop runs log n times, where n is the size of the array.
- This is because the array is divided in half with each iteration (characteristic of binary search).
Calculating Middle Index:
- mid = l + (h - l) / 2: The calculation of the middle index takes constant time O(1) in each iteration.
Comparing Elements:
- The comparisons if (nums[mid] == target), else if (nums[l] <= nums[mid]), and else if (nums[mid] < target && target <= nums[h]):
- Each comparison operation takes constant time O(1).
- These comparisons determine which half of the array to focus on.
Adjusting Pointers:
- Based on the comparisons, the pointers l and h are adjusted using l = mid + 1 or h = mid - 1:
- These adjustments also take constant time O(1) in each iteration.
The overall time complexity is O(log n).
Space Complexity: O(1)
Auxiliary Space Complexity
- The algorithm uses a few integer variables (n, l, h, and mid) to perform the binary search.
- These variables are all of constant space complexity.
- The algorithm does not use any additional data structures that grow with the input size.
- Auxiliary Space Complexity: O(1)
Total Space Complexity
- The total space complexity includes the space taken by the input array nums and any additional space used by the algorithm.
- The input array nums takes O(n) space, where n is the size of the array.
- The auxiliary space used by the algorithm is constant O(1).
- Therefore, the total space complexity is the sum of the input array's space and the auxiliary space.
- Total Space Complexity: O(n) + O(1) = O(n)
Similar Problems
Now we have successfully tackled this problem, let's try these similar problems:-
There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).
Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= 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,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4].
Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums.
You must decrease the overall operation steps as much as possible.
Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0, 1, 2, 4, 5, 6, 7] might become:
- [4,5,6,7,0,1,2] if it was rotated 4 times.
- [0,1,2,4,5,6,7] if it was rotated 7 times.
Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].
Given the sorted rotated array nums of unique elements, return the minimum element of this array.
You must write an algorithm that runs in O(log n) time.