Search Element in a Rotated Sorted Array

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.

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.

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.

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

#include <iostream>
using namespace std;

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;
    cout << "Index of key: " << search(arr, n, key) << 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 mid
        if 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 -1

arr = [4, 5, 6, 7, 0, 1, 2]
key = 0
print("Index of key:", search(arr, key))

public class RotatedArraySearch {
  public static int 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 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;
  }

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

function search(arr, key) {
  let start = 0, end = arr.length - 1;
  while (start <= end) {
    let mid = Math.floor(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;
}

let arr = [4, 5, 6, 7, 0, 1, 2];
let key = 0;
console.log("Index of key:", search(arr, key));

package main

import "fmt"

func search(arr []int, key int) int {
    start, end := 0, len(arr)-1
    for start <= end {
        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
}

func main() {
    arr := []int{4, 5, 6, 7, 0, 1, 2}
    key := 0
    fmt.Println("Index of key:", search(arr, key))
}

fn search(arr: &[i32], key: i32) -> i32 {
    let (mut start, mut end) = (0, arr.len() - 1);
    while start <= end {
        let mid = start + (end - start) / 2;
        if arr[mid] == key {
            return mid as i32;
        }
        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;
            }
        }
    }
    -1
}

fn main() {
    let arr = [4, 5, 6, 7, 0, 1, 2];
    let key = 0;
    let index = search(&arr, key);
    println!("Index of key: {}", index);
}

fun search(arr: IntArray, key: Int): Int {
    var start = 0
    var end = arr.size - 1
    while (start <= end) {
        val 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
}

fun main() {
    val arr = intArrayOf(4, 5, 6, 7, 0, 1, 2)
    val key = 0
    println("Index of key: ${search(arr, key)}")
}

func search(_ arr: [Int], _ key: Int) -> Int {
    var start = 0
    var end = arr.count - 1
    while start <= end {
        let 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
}

let arr = [4, 5, 6, 7, 0, 1, 2]
let key = 0
print("Index of key: \(search(arr, key))")

function search(arr: number[], key: number): number {
  let start = 0, end = arr.length - 1;
  while (start <= end) {
    let mid = Math.floor(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;
}

let arr: number[] = [4, 5, 6, 7, 0, 1, 2];
let key = 0;
console.log("Index of key:", search(arr, key));

Time complexity

Space complexity

O(1)

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