Search in Rotated Sorted Array Using Binary Search - Visualization

Arrays - Binary Search

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

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❯

Understanding the Problem

We are given a rotated sorted array and a target element. Our goal is to find the index of the target using an efficient algorithm.

A rotated sorted array is one where the array was originally sorted in ascending order, but then it was rotated at some pivot. For example, [6, 7, 8, 1, 2, 3, 4] is a rotation of [1, 2, 3, 4, 6, 7, 8].

The challenge here is that binary search requires a sorted array. In a rotated array, only parts of the array are sorted. So we have to modify our binary search approach to handle this.

Step-by-Step Solution with Example

step 1: Choose an example

Let’s work with the example: arr = [6, 7, 8, 1, 2, 3, 4] and target = 2.

step 2: Initialize search range

We set two pointers: start = 0 and end = arr.length - 1.

step 3: Begin binary search loop

While start ≤ end, we calculate the middle index: mid = Math.floor((start + end) / 2).

step 4: Check if mid is the target

If arr[mid] == target, we return mid — we've found the element!

step 5: Decide which half is sorted

  • If arr[start] ≤ arr[mid], then the left half is sorted.
  • If arr[mid] ≤ arr[end], then the right half is sorted.

step 6: Narrow down the search

If the left half is sorted:

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

If the right half is sorted:

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

step 7: Repeat until found or range is empty

Keep repeating steps 3–6 until you either find the target or the range collapses (start > end).

step 8: Apply this to our example

Initial: start = 0, end = 6 → mid = 3 → arr[mid] = 1

Right half [1, 2, 3, 4] is sorted → and target 2 lies in that half → move start = mid + 1 = 4

New mid = (4+6)//2 = 5 → arr[5] = 3

Right half [3, 4] is sorted → target 2 not in this half → move end = mid - 1 = 4

New mid = (4+4)//2 = 4 → arr[4] = 2 — found it!

Return index 4

Edge Cases

  • Empty array: If the array is empty, return -1 immediately.
  • Single element: Compare that element with the target. If it matches, return index 0; else return -1.
  • Target not present: Binary search will terminate with start > end. Return -1.
  • Already sorted array (not rotated): Binary search will still work fine using this logic.

Finally

This approach modifies binary search to handle rotated sorted arrays effectively. By determining which half is sorted at each step and checking where the target lies, we reduce the search space efficiently.

It ensures O(log n) performance and handles all edge cases clearly. Practicing with various examples and edge cases helps strengthen understanding of this clever variation of binary search.

Algorithm Steps❯

  1. Initialize start = 0, end = n - 1.
  2. While start ≤ end, calculate mid = start + (end - start) / 2.
  3. If arr[mid] == key, return mid.
  4. 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.
  5. 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.
  6. If not found, return -1.

Code

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

int 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 mid;

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

int main() {
    int arr[] = {4, 5, 6, 7, 0, 1, 2};
    int n = sizeof(arr)/sizeof(arr[0]);
    int key = 0;
    int index = search(arr, n, key);
    printf("Index of key: %d\n", index);
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(1)The key is found at the first mid-point without needing further comparisons.
Average CaseO(log n)Each step eliminates half the search space using binary search logic.
Worst CaseO(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.


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...