Given a sorted and rotated array (possibly with duplicates), determine if a given key exists in it, returning true if found, otherwise false.
Examples:
Input: arr[] = [3, 3, 3, 1, 2, 3], key = 3
Output: true
Explanation: 3 is present in the array.Input: arr[] = [3, 3, 3, 1, 2, 3], key = 11
Output: false
Explanation: 11 is not present in the given array.
Try it on GfG Practice
Table of Content
[Naive Approach] Using Linear Search - O(n) Time and O(1) Space
A simple approach is to iterate through the array and check for each element, if it matches the target then return the index, otherwise return -1. To know more about the implementation, please refer Introduction to Linear Search Algorithm.
#include <iostream>
#include <vector>
using namespace std;
bool search(vector<int>& arr, int key) {
for (int i = 0; i < arr.size(); i++) {
// Check each element one by one
if (arr[i] == key)
return true;
}
// Key not found
return false;
}
int main() {
vector<int> arr = {3, 3, 3, 1, 2, 3};
int key = 3 ;
bool found = search(arr, key) ;
cout << (found ? "true" : "false") << endl ;
return 0 ;
}
public class GfG {
static boolean search(int[] arr, int key) {
for (int i = 0; i < arr.length; i++) {
// Check each element one by one
if (arr[i] == key)
return true;
}
// Key not found
return false;
}
public static void main(String[] args) {
int[] arr = {3, 3, 3, 1, 2, 3};
int key = 3;
boolean found = search(arr, key);
System.out.println(found ? "true" : "false");
}
}
def search(arr, key):
for i in range(len(arr)):
# Check each element one by one
if arr[i] == key:
return True
# Key not found
return False
if __name__ == "__main__":
arr = [3, 3, 3, 1, 2, 3]
key = 3
found = search(arr, key)
print("true" if found else "false")
using System;
class GFG {
static bool search(int[] arr, int key) {
for (int i = 0; i < arr.Length; i++) {
// Check each element one by one
if (arr[i] == key)
return true;
}
// Key not found
return false;
}
static void Main() {
int[] arr = {3, 3, 3, 1, 2, 3};
int key = 3;
bool found = search(arr, key);
Console.WriteLine(found ? "true" : "false");
}
}
function search(arr, key) {
for (let i = 0; i < arr.length; i++) {
// Check each element one by one
if (arr[i] === key)
return true;
}
// Key not found
return false;
}
// Driver Code
const arr = [3, 3, 3, 1, 2, 3];
const key = 3;
const found = search(arr, key);
console.log(found ? "true" : "false");
[Expected Approach] - Using Binary Search
This approach applies a modified version of binary search directly to the entire rotated array. At every iteration, the middle element is checked against the key. If it’s not the key, we determine whether the left half or right half is sorted by comparing values at arr[lo] and arr[mid]. If the left half is sorted and the key lies within its range, we adjust hi = mid - 1; otherwise, we shift lo = mid + 1. If the right half is sorted and the key lies within its range, we move lo = mid + 1; else, hi = mid - 1.
#include <iostream>
#include <vector>
using namespace std;
bool search(vector<int>& arr, int key) {
int l = 0;
int r = arr.size() - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
// Found key
if (arr[mid] == key)
return true;
// Handle duplicates
if (arr[l] == arr[mid] && arr[mid] == arr[r]) {
l++;
r--;
continue;
}
// Left half is sorted
if (arr[l] <= arr[mid]) {
// Check if key is in left half
if (arr[l] <= key && key < arr[mid])
r = mid - 1;
else
l = mid + 1;
}
// Right half is sorted
else {
// Check if key is in right half
if (arr[mid] < key && key <= arr[r])
l = mid + 1;
else
r = mid - 1;
}
}
return false;
}
int main() {
vector<int> arr = {3, 3, 3, 1, 2, 3};
int key = 3;
if(search(arr, key))
cout<<"true"<<endl;
else
cout<<"false"<<endl;
return 0;
}
public class GfG {
static boolean search(int[] arr, int key) {
int l = 0;
int r = arr.length - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
// Found key
if (arr[mid] == key)
return true;
// Handle duplicates
if (arr[l] == arr[mid] && arr[mid] == arr[r]) {
l++;
r--;
continue;
}
// Left half is sorted
if (arr[l] <= arr[mid]) {
// Check if key is in left half
if (arr[l] <= key && key < arr[mid])
r = mid - 1;
else
l = mid + 1;
}
// Right half is sorted
else {
// Check if key is in right half
if (arr[mid] < key && key <= arr[r])
l = mid + 1;
else
r = mid - 1;
}
}
return false;
}
public static void main(String[] args) {
int[] arr = {3, 3, 3, 1, 2, 3};
int key = 3;
if (search(arr, key))
System.out.println("true");
else
System.out.println("false");
}
}
def search(arr, key):
l = 0
r = len(arr) - 1
while l <= r:
mid = l + (r - l) // 2
# Found key
if arr[mid] == key:
return True
# Handle duplicates
if arr[l] == arr[mid] and arr[mid] == arr[r]:
l += 1
r -= 1
continue
# Left half is sorted
if arr[l] <= arr[mid]:
# Check if key is in left half
if arr[l] <= key and key < arr[mid]:
r = mid - 1
else:
l = mid + 1
# Right half is sorted
else:
# Check if key is in right half
if arr[mid] < key and key <= arr[r]:
l = mid + 1
else:
r = mid - 1
return False
if __name__ == "__main__":
arr = [3, 3, 3, 1, 2, 3]
key = 3
if search(arr, key):
print("true")
else:
print("false")
using System;
class GfG {
static bool search(int[] arr, int key) {
int l = 0;
int r = arr.Length - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
// Found key
if (arr[mid] == key)
return true;
// Handle duplicates
if (arr[l] == arr[mid] && arr[mid] == arr[r]) {
l++;
r--;
continue;
}
// Left half is sorted
if (arr[l] <= arr[mid]) {
// Check if key is in left half
if (arr[l] <= key && key < arr[mid])
r = mid - 1;
else
l = mid + 1;
}
// Right half is sorted
else {
// Check if key is in right half
if (arr[mid] < key && key <= arr[r])
l = mid + 1;
else
r = mid - 1;
}
}
return false;
}
static void Main() {
int[] arr = {3, 3, 3, 1, 2, 3};
int key = 3;
if (search(arr, key))
Console.WriteLine("true");
else
Console.WriteLine("false");
}
}
function search(arr, key) {
let l = 0;
let r = arr.length - 1;
while (l <= r) {
let mid = l + Math.floor((r - l) / 2);
// Found key
if (arr[mid] === key)
return true;
// Handle duplicates
if (arr[l] === arr[mid] && arr[mid] === arr[r]) {
l++;
r--;
continue;
}
// Left half is sorted
if (arr[l] <= arr[mid]) {
// Check if key is in left half
if (arr[l] <= key && key < arr[mid])
r = mid - 1;
else
l = mid + 1;
}
// Right half is sorted
else {
// Check if key is in right half
if (arr[mid] < key && key <= arr[r])
l = mid + 1;
else
r = mid - 1;
}
}
return false;
}
// Driver Code
const arr = [3, 3, 3, 1, 2, 3];
const key = 3;
if (search(arr, key))
console.log("true");
else
console.log("false");
Output
true
Time Complexity: O(n), Its time complexity is O(log n) for most cases but can degrade to O(n) in the worst case when the array contains many duplicates.
Auxiliary Space: O(1)