Binary Search: Search Element in Rotated Sorted Array - I

This chapter focuses on solving the problem of searching for a target element within a rotated sorted array containing unique elements. We will explore why standard binary search fails on rotated arrays, establish the core mathematical intuition to adapt it, and construct an optimal $O(\log N)$ search algorithm.

1. The Problem Context and Definition

A rotated sorted array is an array that was initially sorted in ascending order but has been rotated at a specific pivot point.

Real-Life Analogy: The Circular Carousel

Imagine a numbered deck of cards from $1$ to $9$ laid out in order. If you cut the deck at some point—say, after $6$—and place the first part behind the second part, the sequence becomes: [7, 8, 9, 1, 2, 3, 4, 5, 6]

Though the global sorted order is disrupted, local sorted properties still exist.

Formal Definition

Given a sorted array of unique elements:

If we rotate it at index $3$ (shifting elements after index $3$ to the front), the array becomes:

Problem Statement

Given a rotated sorted array of unique elements and a target value, return the index of the target if it exists in the array. If the target is not present, return -1.

2. The Naive Approach: Linear Search

The most straightforward way to find the target element is to scan the array from left to right, comparing each element with the target.

Algorithm

1. Start at index 0 and iterate through the array up to index n - 1.
2. At each index i, check if arr[i] == target.
3. If a match is found, return i.
4. If the loop finishes without finding the target, return -1.

Complexity Analysis

• Time Complexity: $O(N)$ in the worst-case scenario (e.g., if the target is at the very end of the array or is not present at all).
• Space Complexity: $O(1)$ auxiliary space as no extra memory is allocated.

3. The Core Intuition: Why Binary Search?

In technical interviews, identifying the optimal approach without explicit hints is crucial. The key indicators for using Binary Search in this problem are:

1. The requirement to search for an element.
2. The underlying property of the array being sorted (even if it has been rotated).

Whenever an array is sorted, we can leverage its structure to eliminate half of the search space at each step, reducing our search time from linear $O(N)$ to logarithmic $O(\log N)$.

4. The Core Challenge of Rotated Arrays

In a standard sorted array, we can easily determine which half to eliminate by comparing the target with the mid element:

Standard Binary Search:
[1, 2, 3, 4, 5]  (Target = 5, Mid = 3)
Since Target (5) > Mid (3), we are 100% certain that 5 cannot lie on the left.
We safely eliminate the left half.

However, in a rotated sorted array, this direct comparison fails. Let us look at an example:

Rotated Array: [7, 8, 9, 1, 2, 3, 4, 5, 6]
Indices:        0  1  2  3  4  5  6  7  8
Low = 0, High = 8, Mid = 4 (Value = 2)
Target = 8

If we naively apply standard binary search logic:

• Is Target (8) > Mid (2)? Yes.
• Standard logic dictates that the target must lie on the right side of mid.
• However, the target 8 actually lies on the left side of mid (at index 1).

Why does this happen?

Because the array is rotated, the entire array is not monotonically increasing. The left half [7, 8, 9, 1, 2] contains a rotation point and is not fully sorted. Therefore, we cannot make assumptions about element locations based on a single comparison with mid.

5. The Key Observation: One Half is Always Sorted

To adapt binary search for a rotated sorted array, we must exploit a fundamental property of these arrays:

The Single-Pivot Property: If you split a rotated sorted array at any arbitrary index mid, at least one of the two halves (left or right) is guaranteed to be fully sorted.

Visualizing the Sorted Halves

Let's analyze our example array: [7, 8, 9, 1, 2, 3, 4, 5, 6] with mid at index 4 (value 2):

By identifying which half is sorted, we can reliably check if our target falls within the boundaries of that sorted half. If it does, we search that half; if it does not, we search the other half.

How to Identify the Sorted Half

We compare the element at mid with the boundary elements (low and high):

6. Step-by-Step Evolution of the Algorithm

Once we identify the sorted half, we perform a range check to decide which half to eliminate.

Case 1: The Left Half is Sorted (arr[low] <= arr[mid])

We check if the target lies within the sorted left half:

• Condition: Is arr[low] <= target AND target <= arr[mid]?
  • Yes: The target is guaranteed to be in the left half. Eliminate the right half by setting high = mid - 1.
  • No: The target must be in the right half. Eliminate the left half by setting low = mid + 1.

Case 2: The Right Half is Sorted (arr[mid] <= arr[high])

We check if the target lies within the sorted right half:

• Condition: Is arr[mid] <= target AND target <= arr[high]?
  • Yes: The target is guaranteed to be in the right half. Eliminate the left half by setting low = mid + 1.
  • No: The target must be in the left half. Eliminate the right half by setting high = mid - 1.

7. Complete Flow Walkthrough (Dry Run)

Let us dry run the algorithm with the following inputs:

• Array: [7, 8, 9, 1, 2, 3, 4, 5, 6]
• Target: 1

Step 1: Initialization

• low = 0 (value 7)
• high = 8 (value 6)

Iteration 1:
low = 0, high = 8
mid = (0 + 8) / 2 = 4 (value = 2)

1. Is arr[mid] == target? (2 == 1? No).
2. Identify Sorted Half:
   • Is arr[low] <= arr[mid]? (7 <= 2? No).
   • Therefore, the Right Half is sorted.
3. Range Check on Sorted Right Half:
   • Is arr[mid] <= target AND target <= arr[high]? (2 <= 1 <= 6? No).
   • Since the target is not in the sorted right half, it must be in the left half.
   • Eliminate right half: high = mid - 1 = 3.

Iteration 2:
low = 0, high = 3
mid = (0 + 3) / 2 = 1 (value = 8)

1. Is arr[mid] == target? (8 == 1? No).
2. Identify Sorted Half:
   • Is arr[low] <= arr[mid]? (7 <= 8? Yes).
   • Therefore, the Left Half is sorted.
3. Range Check on Sorted Left Half:
   • Is arr[low] <= target AND target <= arr[mid]? (7 <= 1 <= 8? No).
   • Since the target is not in the sorted left half, it must be in the right half.
   • Eliminate left half: low = mid + 1 = 2.

Iteration 3:
low = 2, high = 3
mid = (2 + 3) / 2 = 2 (value = 9)

1. Is arr[mid] == target? (9 == 1? No).
2. Identify Sorted Half:
   • Is arr[low] <= arr[mid]? (9 <= 9? Yes).
   • Therefore, the Left Half is sorted.
3. Range Check on Sorted Left Half:
   • Is arr[low] <= target AND target <= arr[mid]? (9 <= 1 <= 9? No).
   • Since the target is not in the sorted left half, it must be in the right half.
   • Eliminate left half: low = mid + 1 = 3.

Iteration 4:
low = 3, high = 3
mid = (3 + 3) / 2 = 3 (value = 1)

1. Is arr[mid] == target? (1 == 1? Yes!).
2. Target found at index 3. Return 3.

8. Clean Vertical Workflows

The following diagram illustrates the state transitions of our search boundaries (low, mid, high) during the dry run:

9. Code Implementation

Here are the complete, production-ready implementations in C++ and Java following the exact logical flow discussed.

C++ Implementation

#include <iostream>
#include <vector>

class Solution {
public:
    int search(const std::vector<int>& arr, int target) {
        int n = arr.size();
        int low = 0;
        int high = n - 1;

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

            // 1. Check if mid is the target
            if (arr[mid] == target) {
                return mid;
            }

            // 2. Identify the sorted half
            if (arr[low] <= arr[mid]) {
                // Left half is sorted
                // Check if target lies within the sorted left half
                if (arr[low] <= target && target <= arr[mid]) {
                    high = mid - 1; // Eliminate right half
                } else {
                    low = mid + 1;  // Eliminate left half
                }
            } else {
                // Right half is sorted
                // Check if target lies within the sorted right half
                if (arr[mid] <= target && target <= arr[high]) {
                    low = mid + 1;  // Eliminate left half
                } else {
                    high = mid - 1; // Eliminate right half
                }
            }
        }

        // Target not found
        return -1;
    }
};

int main() {
    Solution solver;
    std::vector<int> arr = {7, 8, 9, 1, 2, 3, 4, 5, 6};
    int target = 1;
    int index = solver.search(arr, target);
    std::cout << "Target found at index: " << index << std::endl;
    return 0;
}

Java Implementation

import java.util.List;
import java.util.Arrays;

public class Solution {
    public int search(int[] arr, int target) {
        int n = arr.length;
        int low = 0;
        int high = n - 1;

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

            // 1. Check if mid is the target
            if (arr[mid] == target) {
                return mid;
            }

            // 2. Identify the sorted half
            if (arr[low] <= arr[mid]) {
                // Left half is sorted
                // Check if target lies within the sorted left half
                if (arr[low] <= target && target <= arr[mid]) {
                    high = mid - 1; // Eliminate right half
                } else {
                    low = mid + 1;  // Eliminate left half
                }
            } else {
                // Right half is sorted
                // Check if target lies within the sorted right half
                if (arr[mid] <= target && target <= arr[high]) {
                    low = mid + 1;  // Eliminate left half
                } else {
                    high = mid - 1; // Eliminate right half
                }
            }
        }

        // Target not found
        return -1;
    }

    public static void main(String[] args) {
        Solution solver = new Solution();
        int[] arr = {7, 8, 9, 1, 2, 3, 4, 5, 6};
        int target = 1;
        int index = solver.search(arr, target);
        System.out.println("Target found at index: " + index);
    }
}

10. Complexity Analysis

Time Complexity

At each iteration of the while loop, we perform a constant number of comparisons ($O(1)$) and eliminate exactly half of the remaining search space.

• Recurrence Relation: $T(N) = T(N/2) + O(1)$
• Worst-case Time Complexity: $O(\log_2 N)$
• Best-case Time Complexity: $O(1)$ (when the mid element on the first iteration is the target).

Space Complexity

• Space Complexity: $O(1)$
• Reason: The algorithm only uses a few pointers (low, high, mid) and performs the search in-place without allocating any additional data structures.

11. Edge Cases and Pitfalls

When implementing this algorithm, pay close attention to the following edge cases to avoid bugs:

1. Array of Size 1: If the array contains only one element, e.g., [1] and target is 1.

   • low = 0, high = 0, mid = 0.
   • arr[mid] == target evaluates to true immediately, returning 0.
   • If target is 5, the loop terminates after one iteration and correctly returns -1.

2. Target Not Present: If the target is completely absent from the array, the search space will shrink until low > high. The loop will terminate, and the code will safely return -1.

3. Integer Overflow: When calculating mid, using (low + high) / 2 can cause integer overflow if the sum of low and high exceeds the maximum value of a 32-bit signed integer.

   Note: Always calculate mid using low + (high - low) / 2 to prevent overflow.

Summary and Key Takeaways

• Rotated Sorted Arrays retain local sorted properties. At any division point mid, at least one half of the array is guaranteed to be sorted.
• Linear Search provides a simple $O(N)$ solution but fails to leverage the sorted nature of the array.
• Binary Search can be adapted to run in $O(\log N)$ time by identifying the sorted half before making elimination decisions.
• The Sorted Half Rule: If arr[low] <= arr[mid], the left half is sorted. Otherwise, the right half is sorted.
• Range Checking: Once the sorted half is identified, check if the target falls within its boundaries. If it does, narrow the search to that half. Otherwise, search the opposite half.
• Unique Elements Constraint: This specific algorithm relies on all elements being unique. (Handling duplicates requires a modified approach, which is covered in the next chapter).