In search in sorted rotated array problem we have given a sorted and rotated array and an element, check if the given element is present in the array or not.
Table of Contents
Examples
Input
nums[] = {2, 5, 6, 0, 0, 1, 2}
target = 0
Output
true
Input
nums[] = {2, 5, 6, 0, 0, 1, 2}
target = 3
Output
false
Naive Approach for Search an Element in Sorted Rotated Array
Linearly traverse in the array and search for the target value.
- Run a loop for i = 0 to n(not included), where n is the number of elements in the array.
- At every iteration, check if nums[i] equal to a target value or not. If it is equal, return true, else continue for the next element.
- If there is no element equals to the target value, return false.
JAVA Code
public class SearchInRotatedAndSortedArray {
private static boolean searchTarget(int[] nums, int target) {
int n = nums.length;
// Traverse the given array and search for the target value
for (int i = 0; i < n; i++) {
if (nums[i] == target) {
return true;
}
}
return false;
}
public static void main(String[] args) {
// Example 1
int nums[] = new int[]{2, 5, 6, 0, 0, 1, 2};
int target = 0;
System.out.println(searchTarget(nums, target));
// Example 2
target = 3;
System.out.println(searchTarget(nums, target));
}
}true false
C++ Code
#include<bits/stdc++.h>
using namespace std;
bool searchTarget(int *nums, int target, int n) {
// Traverse the given array and search for the target value
for (int i = 0; i < n; i++) {
if (nums[i] == target)
return true;
}
return false;
}
int main() {
// Example 1
int nums[] = {2, 5, 6, 0, 0, 1, 2};
int target = 0;
int n = sizeof(nums) / sizeof(nums[0]);
if (searchTarget(nums, target, n)) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
// Example 2
target = 3;
if (searchTarget(nums, target, n)) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
return 0;
}true false
Complexity Analysis for Search an Element in Sorted Rotated Array
Time Complexity = O(n)
Space Complexity = O(1)
where n is the number of elements in the array.
Optimal Approach for Search an Element in Sorted Rotated Array
The array might contain duplicates, so the idea of dividing the array into two sorted arrays will not work.
Let the starting index of the array be l and ending index be h,
- Find the mid, as mid = (l + h) / 2.
- If arr[mid] equals to target value, return true.
- If arr[l] is equals to arr[h] is equals to arr[mid], then increment l and decrement h.
- Else if arr[l] is less than or equals to arr[mid], then the left half is sorted, if the target lies in the range of sorted left half, search in the left half else search in the right half.
- If the above condition is not true, the right half, from mid to h, is sorted, if the target lies in the range of sorted right half, search in right half else search in the left half.
JAVA Code
public class SearchInRotatedAndSortedArray {
private static boolean searchTarget(int[] nums, int target, int l, int h) {
// Index out of bound, element does not exist
if (l > h)
return false;
// Find the middle element
int mid = (l + h) / 2;
// If this is the target element, return true
if (nums[mid] == target) {
return true;
}
// If nums[l] = nums[h] = nums[mid], increment l and decrement h
if (nums[l] == nums[mid] && nums[h] == nums[mid]) {
return searchTarget(nums, target, l + 1, h - 1);
}
// If nums[l] <= nums[mid], left half is sorted
if (nums[l] <= nums[mid]) {
// If the target lies in the first half, search in first half
if (target >= nums[l] && target <= nums[mid]) {
return searchTarget(nums, target, l, mid - 1);
}
// Else search in second half
return searchTarget(nums, target, mid + 1, h);
}
// If first half is not sorted, then second half is sorted
// If the target is present in the second half, search in second half
if (target >= nums[mid] && target <= nums[h]) {
return searchTarget(nums, target, mid + 1, h);
}
// Else search in the first half
return searchTarget(nums, target, l, mid - 1);
}
public static void main(String[] args) {
// Example 1
int nums[] = new int[]{2, 5, 6, 0, 0, 1, 2};
int target = 0;
System.out.println(searchTarget(nums, target, 0, nums.length - 1));
// Example 2
target = 3;
System.out.println(searchTarget(nums, target, 0, nums.length - 1));
}
}true false
C++ Code
#include<bits/stdc++.h>
using namespace std;
bool searchTarget(int *nums, int target, int l, int h) {
// Index out of bound, element does not exist
if (l > h)
return false;
// Find the middle element
int mid = (l + h) / 2;
// If this is the target element, return true
if (nums[mid] == target)
return true;
// If nums[l] = nums[h] = nums[mid], increment l and decrement h
if (nums[l] == nums[mid] && nums[h] == nums[mid]) {
return searchTarget(nums, target, l + 1, h - 1);
}
// If nums[l] <= nums[mid], left half is sorted
if (nums[l] <= nums[mid]) {
// If the target lies in the first half, search in first half
if (target >= nums[l] && target <= nums[mid]) {
return searchTarget(nums, target, l, mid - 1);
}
// Else search in second half
return searchTarget(nums, target, mid + 1, h);
}
// If first half is not sorted, then second half is sorted
// If the target is present in the second half, search in second half
if (target >= nums[mid] && target <= nums[h]) {
return searchTarget(nums, target, mid + 1, h);
}
// Else search in the first half
return searchTarget(nums, target, l, mid - 1);
}
int main() {
// Example 1
int nums[] = {2, 5, 6, 0, 0, 1, 2};
int target = 0;
int n = sizeof(nums) / sizeof(nums[0]);
if (searchTarget(nums, target, 0, n - 1)) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
// Example 2
target = 3;
if (searchTarget(nums, target, 0, n - 1)) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
return 0;
}true false
Complexity Analysis for Search an Element in Sorted Rotated Array
Time Complexity = O(log n)
Space Complexity = O(1)
where n is the number of elements in the array.