Search in Rotated Sorted Array (with Duplicates) Optimal Binary Search

Arrays - Binary Search

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

Problem Statement❯

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.

Examples❯

Input Array Key Output Description
[2, 5, 6, 0, 0, 1, 2] 0 true Key is present after rotation with duplicates
[2, 5, 6, 0, 0, 1, 2] 3 false Key not present in the array
[1, 0, 1, 1, 1] 0 true Key is present, array has many duplicates
[1, 1, 1, 1, 1] 2 false All values are duplicates, key is not present
[1] 1 true Single-element array with match
[1] 0 false Single-element array without match
[] 5 false Empty array, so key cannot be present

Solution❯

Understanding the Problem

We are given a rotated sorted array that may contain duplicate elements. Our goal is to determine if a target number exists in this array.

A rotated sorted array is one that has been shifted at some pivot point. For example, the array [1, 2, 3, 4, 5] might be rotated to become [4, 5, 1, 2, 3]. The twist here is that the array may also contain duplicate values, which makes the traditional binary search approach slightly more complex.

Step-by-Step Solution with Example

Step 1: Start with Binary Search

We initialize two pointers: start at index 0, and end at the last index of the array. The idea is to repeatedly check the middle element and decide whether to move left or right based on sorted properties.

Step 2: Check the Middle Element

Find the middle index using mid = Math.floor((start + end) / 2). If arr[mid] == target, return true.

Step 3: Handle Duplicates at Boundaries

If arr[start] == arr[mid] == arr[end], we can't determine which side is sorted. In such cases, we cautiously move the start pointer forward and the end pointer backward by one step to eliminate duplicates.

Step 4: Determine Which Half is Sorted

If arr[start] <= arr[mid], the left half is sorted.

  • If target lies between arr[start] and arr[mid], narrow the search to the left half: end = mid - 1.
  • Otherwise, search the right half: start = mid + 1.

Step 5: Right Half is Sorted

If the left half isn’t sorted, then the right half must be sorted. Check if the target lies in the range arr[mid] to arr[end].

  • If it does, shift to the right half: start = mid + 1.
  • Else, move to the left half: end = mid - 1.

Step 6: Repeat Until Found or Exhausted

Repeat the above steps while start <= end. If the loop ends without finding the target, return false.

Edge Cases

  • Empty Array: If the input array is empty, the result is immediately false.
  • Single Element: Check if the single element matches the target.
  • All Elements Same: Binary search might degrade to linear time O(n) since we cannot skip chunks based on sorted halves.
  • No Rotation: The array may already be sorted with no rotation — our approach still works correctly.

Finally

This approach enhances binary search to work with rotated arrays and duplicates. Though average-case complexity is O(log n), it can degrade to O(n) in the worst case due to duplicates. Still, it handles all key scenarios:

  • Fully sorted or rotated arrays
  • Presence of duplicates
  • Tricky ambiguous cases with same start, mid, and end values

Always take time to understand the problem's structure and apply conditional logic carefully when standard binary search rules don't apply.

Algorithm Steps❯

  1. Start with start = 0 and end = n - 1.
  2. While start ≤ end, compute mid = start + (end - start) / 2.
  3. If arr[mid] == key, return true.
  4. If arr[start] == arr[mid] == arr[end], increment start and decrement end.
  5. Else, check if left half is sorted (i.e., arr[start] ≤ arr[mid]).
  6. → If yes, and arr[start] ≤ key < arr[mid], move end = mid - 1.
  7. → Else, move start = mid + 1.
  8. If right half is sorted (i.e., arr[mid] ≤ arr[end]):
  9. → If arr[mid] < key ≤ arr[end], move start = mid + 1.
  10. → Else, move end = mid - 1.
  11. Repeat until found or range becomes invalid.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <stdbool.h>

bool search(int arr[], int n, int key) {
  int start = 0, end = n - 1;
  while (start <= end) {
    int mid = start + (end - start) / 2;
    if (arr[mid] == key) return true;

    if (arr[start] == arr[mid] && arr[mid] == arr[end]) {
      start++;
      end--;
    } else if (arr[start] <= arr[mid]) {
      if (arr[start] <= key && key < arr[mid])
        end = mid - 1;
      else
        start = mid + 1;
    } else {
      if (arr[mid] < key && key <= arr[end])
        start = mid + 1;
      else
        end = mid - 1;
    }
  }
  return false;
}

int main() {
  int arr[] = {2, 5, 6, 0, 0, 1, 2};
  int key = 0;
  int n = sizeof(arr) / sizeof(arr[0]);
  printf("Is Key Present: %s\n", search(arr, n, key) ? "true" : "false");
  return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(1)Key is found at the middle index in the first check.
Average CaseO(log n)Binary search generally divides the array in half at each step.
Worst CaseO(n)When duplicates exist everywhere, we might need to linearly shrink the search range.

Space Complexity❯

O(1)

Explanation: Only a constant number of pointers are used for binary search, without extra space.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...