Search in Rotated Sorted Array
Using Binary Search

⬅ Previous Topic

Next Topic ⮕

Search in Rotated Sorted Array with Duplicates

Topic Contents

Problem Examples Solution Visualization Algorithm Code Time Space

Problem Statement

Given a rotated sorted array and a target value key, your task is to find the index of the target using an optimal binary search approach.

A rotated sorted array is a sorted array that has been rotated at some unknown pivot. For example, [4, 5, 6, 7, 0, 1, 2] is a rotation of [0, 1, 2, 4, 5, 6, 7].

If the element is found, return its index. Otherwise, return -1.

Examples❯

Input Array	Key	Output Index	Description
[4, 5, 6, 7, 0, 1, 2]	0	4	0 is present after the pivot point
[4, 5, 6, 7, 0, 1, 2]	6	2	6 is found before the rotation point
[1]	1	0	Single element array, match found
[1]	0	-1	Single element array, target not present
[1, 3]	3	1	Simple rotated array of two elements
[6, 7, 8, 1, 2, 3, 4, 5]	3	5	Target lies in the rotated right half
[]	10	-1	Empty array, element cannot be found
[30, 40, 50, 10, 20]	10	3	Rotation in the middle, target found
[30, 40, 50, 10, 20]	60	-1	Target does not exist

Solution❯

To efficiently search in a rotated sorted array, we use a modified version of binary search. Although the array isn't fully sorted due to the rotation, we can still take advantage of the fact that at least one half of the array (either left or right) is always sorted.

Understanding the Problem

In a regular binary search, we look for the target by checking if it lies in the left or right half, since the array is sorted. In a rotated sorted array, that logic needs adjustment. At every step, we still check the middle element, but also identify which half is sorted, and whether the target lies within that sorted half.

What Cases Can Occur?

Case 1: The element at mid is the key — In this case, we simply return the index.
Case 2: The left half is sorted — This means arr[start] ≤ arr[mid]. Now:
- If the key lies between arr[start] and arr[mid], then we discard the right half by moving end = mid - 1.
- Otherwise, we move start = mid + 1 to search in the unsorted right half.
Case 3: The right half is sorted — This means arr[mid] ≤ arr[end]. Then:
- If the key lies between arr[mid] and arr[end], we search the right half by setting start = mid + 1.
- Otherwise, move end = mid - 1 to check the left half.
Case 4: Empty array — If the array is empty, we immediately return -1 because there's nothing to search.
Case 5: Single element — We directly compare it with the key. If it matches, return 0; otherwise, return -1.

Why This Works

This approach works in O(log n) time because we effectively discard half the array in every step, just like standard binary search. By checking which half is sorted and narrowing the range intelligently, we find the target if it exists.

It’s a very efficient way to deal with rotated arrays, and works well even for large datasets.

Visualization

Algorithm Steps

Initialize start = 0, end = n - 1.
While start ≤ end, calculate mid = start + (end - start) / 2.
If arr[mid] == key, return mid.
If the left half arr[start] ≤ arr[mid] is sorted:

Check if key lies between arr[start] and arr[mid].
If yes, move end = mid - 1.
Else, move start = mid + 1.

If the right half is sorted:

Check if key lies between arr[mid] and arr[end].
If yes, move start = mid + 1.
Else, move end = mid - 1.

If not found, return -1.

Code

Java

Python

JavaScript

C++

Kotlin

Swift

Php

public class RotatedArraySearch {
  public static int search(int[] arr, int key) {
    int start = 0;
    int end = arr.length - 1;

    while (start <= end) {
      int mid = start + (end - start) / 2;

      if (arr[mid] == key) return mid;

      // Left half is sorted
      if (arr[start] <= arr[mid]) {
        if (key >= arr[start] && key < arr[mid]) {
          end = mid - 1;
        } else {
          start = mid + 1;
        }
      }
      // Right half is sorted
      else {
        if (key > arr[mid] && key <= arr[end]) {
          start = mid + 1;
        } else {
          end = mid - 1;
        }
      }
    }
    return -1;
  }

  public static void main(String[] args) {
    int[] arr = {4, 5, 6, 7, 0, 1, 2};
    int key = 0;
    int index = search(arr, key);
    System.out.println("Index of key: " + index);
  }
}

Time Complexity

Case	Time Complexity	Explanation
Best Case	O(1)	The key is found at the first mid-point without needing further comparisons.
Average Case	O(log n)	Each step eliminates half the search space using binary search logic.
Worst Case	O(log n)	In the worst case, the search continues until one element remains.

Space Complexity

O(1)

Explanation: The algorithm uses a constant number of variables, no extra memory.

⬅ Previous Topic

Count Occurrences in Sorted Array

Next Topic ⮕

Search in Rotated Sorted Array with Duplicates

Overview of Techniques14
❯

Sorting6
❯

Arrays32
❯

Arrays - Binary Search28
❯

Strings18
❯

Matrix3
❯

Matrix - Binary Search5
❯

Binary Trees36
❯

Binary Search Trees14
❯

Graphs46
❯

Tries1
❯

Search in Rotated Sorted Array
Using Binary Search

Problem Statement

Examples❯

Solution❯

Understanding the Problem

What Cases Can Occur?

Why This Works

Visualization

Algorithm Steps

Code

Time Complexity

Space Complexity

Support ProgramGuru.org❯

Search in Rotated Sorted ArrayUsing Binary Search

Problem Statement

Examples❯

Solution❯

Understanding the Problem

What Cases Can Occur?

Why This Works

Visualization

Algorithm Steps

Code

Time Complexity

Space Complexity

Welcome to ProgramGuru

Support ProgramGuru.org❯

Search in Rotated Sorted Array
Using Binary Search