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

1. Find mid → decide which half is sorted.
2. Check if target lies in sorted half.
3. 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:

1. Find peak (maximum element)
2. Apply binary search on ascending part
3. 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;
}

Problems to practice:

• LeetCode 33, 81 → rotated array search
• LeetCode 153 → find minimum in rotated sorted array
• LeetCode 1095 → find in rotated sorted array II (duplicates)
• LeetCode 1095 → mountain array search

---

5. Tips & Edge Cases

1. Always check for duplicates in rotated arrays.
2. For single-element arrays, check if arr.length == 1.
3. Peak-finding in bitonic arrays → use < comparison to find correct slope.
4. Mind integer overflow in mid calculation.

---

✅ Blog 3 Summary:

• Rotated sorted array search
• Pivot finding
• Handling duplicates
• Bitonic / mountain array search

---

Next in Series — Blog 4

Binary Search in 2D / Matrix & Advanced Variants:

• Row-wise and column-wise sorted matrix
• Flatten 2D to 1D for binary search
• Infinite array search
• Ternary search for unimodal functions