Search in Rotated Sorted Array with Duplicates

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.

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.

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.

#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;
}

#include <iostream>
using namespace std;

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]);
  cout << "Is Key Present: " << (search(arr, n, key) ? "true" : "false") << endl;
  return 0;
}

def search(arr, key):
    start, end = 0, len(arr) - 1
    while start <= end:
        mid = start + (end - start) // 2
        if arr[mid] == key:
            return True
        if arr[start] == arr[mid] == arr[end]:
            start += 1
            end -= 1
        elif arr[start] <= arr[mid]:
            if arr[start] <= key < arr[mid]:
                end = mid - 1
            else:
                start = mid + 1
        else:
            if arr[mid] < key <= arr[end]:
                start = mid + 1
            else:
                end = mid - 1
    return False

arr = [2, 5, 6, 0, 0, 1, 2]
key = 0
print("Is Key Present:", search(arr, key))

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;
      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;
  }
  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));
  }
}

function search(arr, key) {
  let start = 0, end = arr.length - 1;
  while (start <= end) {
    const mid = Math.floor((start + end) / 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;
}
const arr = [2, 5, 6, 0, 0, 1, 2];
const key = 0;
console.log("Is Key Present:", search(arr, key));

package main
import "fmt"
func search(arr []int, key int) bool {
  start, end := 0, len(arr)-1
  for start <= end {
    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
}
func main() {
  arr := []int{2, 5, 6, 0, 0, 1, 2}
  key := 0
  fmt.Println("Is Key Present:", search(arr, key))
}

fn search(arr: &[i32], key: i32) -> bool {
    let (mut start, mut end) = (0, arr.len() - 1);
    while start <= end {
        let mid = start + (end - start) / 2;
        if arr[mid] == key {
            return true;
        }
        if arr[start] == arr[mid] && arr[mid] == arr[end] {
            start += 1;
            end -= 1;
        } else if arr[start] <= arr[mid] {
            if arr[start] <= key && key < arr[mid] {
                if mid == 0 { break; }
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        } else {
            if arr[mid] < key && key <= arr[end] {
                start = mid + 1;
            } else {
                if mid == 0 { break; }
                end = mid - 1;
            }
        }
    }
    false
}
fn main() {
    let arr = vec![2, 5, 6, 0, 0, 1, 2];
    let key = 0;
    println!("Is Key Present: {}", search(&arr, key));
}

fun search(arr: IntArray, key: Int): Boolean {
    var start = 0
    var end = arr.size - 1
    while (start <= end) {
        val 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
}
fun main() {
    val arr = intArrayOf(2, 5, 6, 0, 0, 1, 2)
    val key = 0
    println("Is Key Present: ${search(arr, key)}")
}

func search(_ arr: [Int], _ key: Int) -> Bool {
    var start = 0, end = arr.count - 1
    while start <= end {
        let mid = start + (end - start) / 2
        if arr[mid] == key {
            return true
        }
        if arr[start] == arr[mid] && arr[mid] == arr[end] {
            start += 1
            end -= 1
        } 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
}
let arr = [2, 5, 6, 0, 0, 1, 2]
let key = 0
print("Is Key Present: \(search(arr, key))")

function search(arr: number[], key: number): boolean {
  let start = 0, end = arr.length - 1;
  while (start <= end) {
    const mid = Math.floor((start + end) / 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;
}
const arr = [2, 5, 6, 0, 0, 1, 2];
const key = 0;
console.log("Is Key Present:", search(arr, key));

Time complexity

Space complexity

O(1)

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