Binary Search Patterns Series — Blog 3: Rotated & Special Arrays

1. Rotated Sorted Array (Single Rotation)

Problem:
An array is sorted but rotated at some pivot. Search for a target element in O(log n).

Example: [4,5,6,7,0,1,2], target = 0 → Output: 4

1.1 Approach

Find mid → decide which half is sorted.
Check if target lies in sorted half.
Move low or high accordingly.

public int searchRotated(int[] arr, int target) {
    int low = 0, high = arr.length - 1;

    while (low <= high) {
        int mid = low + (high - low)/2;

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

        if (arr[low] <= arr[mid]) { // left half sorted
            if (target >= arr[low] && target < arr[mid]) high = mid - 1;
            else low = mid + 1;
        } else { // right half sorted
            if (target > arr[mid] && target <= arr[high]) low = mid + 1;
            else high = mid - 1;
        }
    }
    return -1;
}

Edge Cases:

Duplicates may require additional checks
Single-element arrays

2. Finding Pivot in Rotated Array

Sometimes you need the rotation index first.

public int findPivot(int[] arr) {
    int low = 0, high = arr.length - 1;
    while (low < high) {
        int mid = low + (high - low)/2;
        if (arr[mid] > arr[high]) low = mid + 1;
        else high = mid;
    }
    return low; // index of smallest element
}

Use Case: Split the array at pivot and apply normal binary search on one half.

3. Rotated Array with Duplicates

Check arr[low] == arr[mid] == arr[high] → cannot decide sorted half, increment low and decrement high.
Else → same logic as single rotation.

4. Bitonic / Mountain Array Search

Problem: Array first increases then decreases. Find a target.

Steps:

Find peak (maximum element)
Apply binary search on ascending part
Apply binary search on descending part

public int searchBitonic(int[] arr, int target) {
    int peak = findPeak(arr);
    int idx = binarySearchAsc(arr, 0, peak, target);
    if (idx != -1) return idx;
    return binarySearchDesc(arr, peak+1, arr.length-1, target);
}

private int findPeak(int[] arr) {
    int low = 0, high = arr.length-1;
    while (low < high) {
        int mid = low + (high-low)/2;
        if (arr[mid] < arr[mid+1]) low = mid+1;
        else high = mid;
    }
    return low;
}

private int binarySearchAsc(int[] arr, int low, int high, int target) {
    while (low <= high) {
        int mid = low + (high-low)/2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) low = mid+1;
        else high = mid-1;
    }
    return -1;
}

private int binarySearchDesc(int[] arr, int low, int high, int target) {
    while (low <= high) {
        int mid = low + (high-low)/2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] > target) low = mid+1;
        else high = mid-1;
    }
    return -1;
}