Problem Statement: There is an integer array nums sorted in ascending order (with distinct values). Given the array nums after the possible clockwise rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums. We need to search a given element in a rotated sorted array.
Example 1:
Input: nums = [4,5,6,7,0,1,2,3], target = 0 Output: 4 Explanation: Here, the target is 0. We can see that 0 is present in the given rotated sorted array, nums. Thus, we get output as 4, which is the index at which 0 is present in the array.
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3 Output: -1 Explanation: Here, the target is 3. Since 3 is not present in the given rotated sorted array. Thus, we get output as -1.
Solution:
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Solution 1: Using Linear Search
Approach :
We will iterate through the array completely. While iterating, we have to check if we have found the target element in the array. If we find it, we will return its index. If we iterate completely and still do not find an element in the array. This indicates the target is not present and hence we return -1 as mentioned in the question.
Code:
C++ Code
#include<bits/stdc++.h>
using namespace std;
int search(vector<int>& nums,int target) {
for(int i=0;i<nums.size();i++)
{
if(nums[i]==target)
return i;
}
return -1;
}
int main() {
vector<int> nums = {4,5,6,7,0,1,2,3};
int target = 3;
cout<<"The index in which the target is present is "<<search(nums,target);
return 0;
}
Time Complexity : O(N)
Reason: We have to iterate through the entire array to check if the target is present in the array.
Space Complexity: O(1)
Reason: We have not used any extra data structures, this makes space complexity, even in the worst case as O(1).
Java Code
import java.util.*;
public class Main {
static int search(int arr[],int target) {
for(int i=0;i<arr.length;i++)
{
if(arr[i]==target)
return i;
}
return -1;
}
public static void main(String args[]) {
int arr[] = {4,5,6,7,0,1,2,3};
int target = 3;
System.out.println("The index in which the number is present is "+search(arr,target));
}
}
Time Complexity : O(N)
Reason: We have to iterate through the entire array to check if the target is present in the array.
Space Complexity: O(1)
Reason: We have not used any extra data structures, this makes space complexity, even in the worst case as O(1).
Python Code
from typing import List
def search(nums: List[int], target: int) -> int:
for i in range(len(nums)):
if nums[i] == target:
return i
return -1
if __name__ == "__main__":
nums = [4, 5, 6, 7, 0, 1, 2, 3]
target = 3
print("The index in which the target is present is", search(nums, target))Time Complexity : O(N)
Reason: We have to iterate through the entire array to check if the target is present in the array.
Space Complexity: O(1)
Reason: We have not used any extra data structures, this makes space complexity, even in the worst case as O(1).
Solution 2: Using Binary Search
Intuition :
It is mentioned that the array given is sorted but in a rotated manner. So, we can divide a given array into two parts that are sorted. This gives us hints to use binary search. We can visualize a given array to be composed of two sorted arrays.
Approach :
We divide the array into parts. It is done using two pointers, low and high, and dividing the range between them by 2. This gives the midpoint of the range. Check if the target is present in the midpoint, calculated before, of the array. If not present, check if the left half of the array is sorted. This implies that binary search can be applied in the left half of the array provided the target lies between the value range. Else check into the right half of the array. Repeat the above steps until low <= high. If low > high indicates we have searched the array and the target is not present hence return -1. Thus, it makes search operations less as we check the range first and then perform searching in possible ranges which may have target values.
Code:
C++ Code
#include<bits/stdc++.h>
using namespace std;
int search(vector < int > & nums, int target) {
int low = 0, high = nums.size() - 1; //<---step 1
while (low <= high) { //<--- step 2
int mid = (low + high) >> 1; //<----step 3
if (nums[mid] == target)
return mid; // <---step 4
if (nums[low] <= nums[mid]) { //<---step 5
if (nums[low] <= target && nums[mid] >= target)
high = mid - 1; //<---step 6
else
low = mid + 1; //<---step 7
} else { //<---step 7
if (nums[mid] <= target && target <= nums[high])
low = mid + 1;
else
high = mid - 1;
}
}
return -1; //<---step 8
}
int main() {
vector<int> nums = {4,5,6,7,0,1,2,3};
int target = 3;
cout << "The index in which the target is present is " << search(nums, target);
return 0;
}Output: The index in which the target is present is 7
Time Complexity: O(log(N))
Reason: We are performing a binary search, which turns time complexity to O(log(N)) where N is the size of the array.
Space Complexity: O(1)
Reason: We do not use any extra data structure, this turns space complexity to O(1).
Java Code
import java.util.*;
public class Main {
static int search(int arr[], int target) {
int low = 0, high = arr.length - 1; //<---step 1
while (low <= high) { //<--- step 2
int mid = (low + high) >> 1; //<----step 3
if (arr[mid] == target)
return mid; // <---step 4
if (arr[low] <= arr[mid]) { //<---step 5
if (arr[low] <= target && arr[mid] >= target)
high = mid - 1; //<---step 6
else
low = mid + 1; //<---step 7
} else { //<---step 7
if (arr[mid] <= target && target <= arr[high])
low = mid + 1;
else
high = mid - 1;
}
}
return -1; //<---step 8
}
public static void main(String args[]) {
int arr[] = {4,5,6,7,0,1,2,3};
int target = 3;
System.out.println("The index in which the number is present is " + search(arr, target));
}
}Output: The index in which the target is present is 7
Time Complexity: O(log(N))
Reason: We are performing a binary search, which turns time complexity to O(log(N)) where N is the size of the array.
Space Complexity: O(1)
Reason: We do not use any extra data structure, this turns space complexity to O(1).
Python Code
from typing import List
def search(nums: List[int], target: int) -> int:
low = 0
high = len(nums) - 1
while low <= high:
mid = (low + high) >> 1
if nums[mid] == target:
return mid
if nums[low] <= nums[mid]:
if nums[low] <= target and nums[mid] >= target:
high = mid - 1
else:
low = mid + 1
else:
if nums[mid] <= target and target <= nums[high]:
low = mid + 1
else:
high = mid - 1
return -1
if __name__ == "__main__":
nums = [4, 5, 6, 7, 0, 1, 2, 3]
target = 3
print("The index in which the target is present is", search(nums, target))Output: The index in which the target is present is 7
Time Complexity: O(log(N))
Reason: We are performing a binary search, which turns time complexity to O(log(N)) where N is the size of the array.
Space Complexity: O(1)
Reason: We do not use any extra data structure, this turns space complexity to O(1).
Special thanks to Dewanshi Paul and Sudip Ghosh for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article