⬅ Previous Topic
Search Element in a Rotated Sorted ArrayNext Topic ⮕
Minimum in Rotated Sorted Array⬅ Previous Topic
Search Element in a Rotated Sorted ArrayNext Topic ⮕
Minimum in Rotated Sorted ArrayTopic Contents
You are given a rotated sorted array that may contain duplicate values, and a target number key
. Your task is to determine whether the key exists in the array or not.
The array was originally sorted in ascending order but then rotated at some pivot point. Due to rotation and the presence of duplicates, the structure can be irregular.
Your goal: Return true
if the key is found, else return false
.
start = 0
and end = n - 1
.start ≤ end
, compute mid = start + (end - start) / 2
.arr[mid] == key
, return true
.arr[start] == arr[mid] == arr[end]
, increment start
and decrement end
.arr[start] ≤ arr[mid]
).arr[start] ≤ key < arr[mid]
, move end = mid - 1
.start = mid + 1
.arr[mid] ≤ arr[end]
):arr[mid] < key ≤ arr[end]
, move start = mid + 1
.end = mid - 1
.public class RotatedArraySearchWithDuplicates {
public static boolean search(int[] arr, int key) {
int start = 0, end = arr.length - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (arr[mid] == key) return true;
// Handle duplicates: shrink window
if (arr[start] == arr[mid] && arr[mid] == arr[end]) {
start++;
end--;
}
// Left half is sorted
else if (arr[start] <= arr[mid]) {
if (arr[start] <= key && key < arr[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
}
// Right half is sorted
else {
if (arr[mid] < key && key <= arr[end]) {
start = mid + 1;
} else {
end = mid - 1;
}
}
}
return false;
}
public static void main(String[] args) {
int[] arr = {2, 5, 6, 0, 0, 1, 2};
int key = 0;
System.out.println("Is Key Present: " + search(arr, key));
}
}
Case | Time Complexity | Explanation |
---|---|---|
Best Case | O(1) | Key is found at the middle index in the first check. |
Average Case | O(log n) | Binary search generally divides the array in half at each step. |
Worst Case | O(n) | When duplicates exist everywhere, we might need to linearly shrink the search range. |
O(1)
Explanation: Only a constant number of pointers are used for binary search, without extra space.
⬅ Previous Topic
Search Element in a Rotated Sorted ArrayNext Topic ⮕
Minimum in Rotated Sorted ArrayYou can support this website with a contribution of your choice.
When making a contribution, mention your name, and programguru.org in the message. Your name shall be displayed in the sponsors list.