Search in Rotated Arrays

Overview

A rotated sorted array results from taking a sorted array and rotating it around some pivot point. For example, the sorted array [0, 1, 2, 4, 5, 6, 7] rotated at index 4 becomes [4, 5, 6, 7, 0, 1, 2]. The rotation operation preserves the sorted order within each segment but creates a discontinuity at the rotation point.

The search problem requires finding a target element in such an array. The challenge lies in maintaining logarithmic time complexity despite the rotation disrupting the standard binary search assumption of complete sorted order. A naive linear scan achieves O(n) time, but modified binary search approaches can achieve O(log n) by identifying which portion of the array remains sorted at each step.

The problem appears frequently in technical interviews and has practical applications in circular buffers, log rotation systems, and scenarios where sorted data undergoes periodic reorganization. The rotated array structure also models real-world situations like scheduling systems that wrap around (days of the week, hours in a day) or ring buffers in networking.

# Standard sorted array
sorted = [1, 2, 3, 4, 5, 6, 7]

# Same array rotated at index 4
rotated = [5, 6, 7, 1, 2, 3, 4]

# The rotation preserves sorted segments
# Left segment: [5, 6, 7] - sorted
# Right segment: [1, 2, 3, 4] - sorted

The key insight involves recognizing that at least one half of any subarray in a rotated sorted array remains sorted. Binary search divides the array in half, and examining the middle element reveals which half maintains sorted order. This sorted half can then be checked using standard binary search logic, while the unsorted half requires recursive application of the same strategy.

Key Principles

Binary Search Foundation: The algorithm builds on binary search but adapts the comparison logic. Standard binary search assumes complete sorted order, using middle element comparison to eliminate half the search space. Rotated arrays require additional checks to determine which half remains sorted before applying elimination logic.

Sorted Segment Identification: At any division point, comparing the leftmost, middle, and rightmost elements reveals which segment maintains sorted order. If array[left] <= array[mid], the left half is sorted. Otherwise, the right half must be sorted. This invariant holds because rotation creates exactly one discontinuity point.

Two-Phase Comparison: After identifying the sorted segment, the algorithm performs two checks:

1. Determine if the target falls within the sorted segment's range
2. If yes, search that segment; if no, search the opposite segment

This strategy ensures each iteration eliminates half the remaining elements, maintaining O(log n) complexity.

Duplicate Handling Complexity: Arrays with duplicate elements complicate the sorted segment identification. When array[left] == array[mid] == array[right], the algorithm cannot determine which half is sorted without additional checks. This degrades worst-case performance to O(n) for arrays with many duplicates.

# Identifying sorted segments
def find_sorted_segment(arr, left, right, mid)
  # Left segment sorted
  if arr[left] <= arr[mid]
    return :left
  # Right segment sorted
  elsif arr[mid] <= arr[right]
    return :right
  end
end

arr = [4, 5, 6, 7, 0, 1, 2]
left, right = 0, 6
mid = (left + right) / 2  # => 3

# arr[0] = 4, arr[3] = 7, arr[6] = 2
# Since 4 <= 7, left segment [4,5,6,7] is sorted

Target Range Determination: Once the sorted segment is identified, check if the target value falls within its range. For a sorted left segment, verify array[left] <= target <= array[mid]. For a sorted right segment, verify array[mid] <= target <= array[right]. Range checks use standard comparison operators without special rotation logic.

Rotation Point Properties: The rotation point (minimum element) marks where the discontinuity occurs. Elements before this point belong to the higher sorted segment, and elements after belong to the lower sorted segment. Finding the rotation point itself is a related problem that uses similar binary search modifications.

Single Element Edge Case: Arrays with one element trivially solve the search problem. Arrays with two elements require special handling to avoid infinite loops when calculating the midpoint.

Ruby Implementation

Ruby's array indexing and comparison operators make implementing rotated array search straightforward. The standard approach uses iterative binary search with custom comparison logic.

def search_rotated(nums, target)
  left = 0
  right = nums.length - 1
  
  while left <= right
    mid = (left + right) / 2
    
    # Found target
    return mid if nums[mid] == target
    
    # Determine which segment is sorted
    if nums[left] <= nums[mid]
      # Left segment is sorted
      if nums[left] <= target && target < nums[mid]
        # Target is in sorted left segment
        right = mid - 1
      else
        # Target is in unsorted right segment
        left = mid + 1
      end
    else
      # Right segment is sorted
      if nums[mid] < target && target <= nums[right]
        # Target is in sorted right segment
        left = mid + 1
      else
        # Target is in unsorted left segment
        right = mid - 1
      end
    end
  end
  
  -1  # Target not found
end

# Example usage
arr = [4, 5, 6, 7, 0, 1, 2]
search_rotated(arr, 0)  # => 4
search_rotated(arr, 3)  # => -1

Ruby's division operator performs integer division automatically, eliminating the need for explicit floor operations when calculating the midpoint. The <= comparisons handle arrays with duplicate elements at boundaries, though this doesn't fully solve the duplicate problem.

For recursive implementations, Ruby's method call overhead is higher than iteration, but the code expresses the divide-and-conquer logic more explicitly:

def search_rotated_recursive(nums, target, left = 0, right = nums.length - 1)
  return -1 if left > right
  
  mid = (left + right) / 2
  return mid if nums[mid] == target
  
  if nums[left] <= nums[mid]
    # Left segment sorted
    if nums[left] <= target && target < nums[mid]
      search_rotated_recursive(nums, target, left, mid - 1)
    else
      search_rotated_recursive(nums, target, mid + 1, right)
    end
  else
    # Right segment sorted
    if nums[mid] < target && target <= nums[right]
      search_rotated_recursive(nums, target, mid + 1, right)
    else
      search_rotated_recursive(nums, target, left, mid - 1)
    end
  end
end

Handling duplicates requires additional logic to skip over equal elements when the sorted segment cannot be determined:

def search_rotated_with_duplicates(nums, target)
  left = 0
  right = nums.length - 1
  
  while left <= right
    mid = (left + right) / 2
    
    return mid if nums[mid] == target
    
    # Cannot determine sorted segment
    if nums[left] == nums[mid] && nums[mid] == nums[right]
      left += 1
      right -= 1
      next
    end
    
    if nums[left] <= nums[mid]
      if nums[left] <= target && target < nums[mid]
        right = mid - 1
      else
        left = mid + 1
      end
    else
      if nums[mid] < target && target <= nums[right]
        left = mid + 1
      else
        right = mid - 1
      end
    end
  end
  
  -1
end

# Example with duplicates
arr = [2, 5, 6, 0, 0, 1, 2]
search_rotated_with_duplicates(arr, 0)  # => 3 or 4

A functional approach using Ruby's enumeration methods sacrifices performance but provides clarity:

def search_rotated_functional(nums, target)
  nums.each_with_index do |num, idx|
    return idx if num == target
  end
  -1
end

This linear search serves as a fallback for edge cases or when the array is too small to benefit from binary search overhead.

Ruby arrays support negative indexing, but rotated array algorithms use standard positive indices to maintain consistency with the mathematical formulation. Converting between representations adds unnecessary complexity.

Performance Considerations

Time Complexity: The modified binary search achieves O(log n) time complexity for arrays without duplicates. Each iteration eliminates half the remaining search space by identifying which segment is sorted and whether the target falls within it. This matches standard binary search performance despite the rotation.

Arrays with duplicates degrade to O(n) worst case when all elements are identical except the target. The algorithm must increment left and decrement right pointers linearly when unable to determine which segment is sorted, eliminating the logarithmic guarantee.

require 'benchmark'

def generate_rotated_array(size, rotation_point)
  sorted = (1..size).to_a
  sorted.rotate(rotation_point)
end

# Benchmark comparison
Benchmark.bm(20) do |x|
  arr_1000 = generate_rotated_array(1000, 500)
  arr_10000 = generate_rotated_array(10000, 5000)
  arr_100000 = generate_rotated_array(100000, 50000)
  
  x.report("Binary (n=1000):") do
    1000.times { search_rotated(arr_1000, -1) }
  end
  
  x.report("Binary (n=10000):") do
    1000.times { search_rotated(arr_10000, -1) }
  end
  
  x.report("Binary (n=100000):") do
    1000.times { search_rotated(arr_100000, -1) }
  end
end

Space Complexity: The iterative implementation uses O(1) additional space, storing only pointer variables. The recursive implementation requires O(log n) stack space for the call stack, matching the recursion depth. For large arrays, iteration avoids stack overflow risks.

Comparison Count Analysis: Each iteration performs 3-4 comparisons: one to check if target is found, one to determine which segment is sorted, and 1-2 to check if target falls within the sorted segment's range. This constant factor is slightly higher than standard binary search but maintains the same asymptotic complexity.

Cache Performance: Rotated array search exhibits poor cache locality compared to sequential scans. The binary search pattern jumps between distant array indices, causing cache misses. For small arrays that fit in L1 cache, linear search may outperform binary search due to better spatial locality.

# Linear search competitive for small arrays
def linear_search(nums, target)
  nums.index(target) || -1
end

# Crossover point testing
small_arr = generate_rotated_array(20, 10)
Benchmark.bm(15) do |x|
  x.report("Binary small:") do
    10000.times { search_rotated(small_arr, -1) }
  end
  
  x.report("Linear small:") do
    10000.times { linear_search(small_arr, -1) }
  end
end

Branch Prediction: Modern CPUs struggle with the conditional branches in rotated array search because the pattern of which segment is sorted varies unpredictably based on the rotation point and target location. This unpredictability stalls the CPU pipeline, adding latency to each comparison.

Early Termination: Finding the target at the midpoint on the first check provides best-case O(1) performance. This occurs when the rotation point happens to place the target at the array's center. Average case still performs O(log n) comparisons.

Practical Examples

Finding Configuration Values: A configuration system stores timestamped settings in a circular buffer. As new configurations arrive, they overwrite old entries, creating a rotated sorted structure. Searching for a configuration by timestamp requires the rotated search algorithm.

class ConfigurationRing
  def initialize(capacity)
    @buffer = Array.new(capacity)
    @timestamps = Array.new(capacity)
    @write_pos = 0
    @size = 0
  end
  
  def add_config(timestamp, config)
    @timestamps[@write_pos] = timestamp
    @buffer[@write_pos] = config
    @write_pos = (@write_pos + 1) % @buffer.length
    @size = [@size + 1, @buffer.length].min
  end
  
  def find_by_timestamp(target_ts)
    # Timestamps form rotated sorted array
    idx = search_rotated_timestamps(@timestamps, target_ts)
    idx == -1 ? nil : @buffer[idx]
  end
  
  private
  
  def search_rotated_timestamps(timestamps, target)
    left, right = 0, @size - 1
    
    while left <= right
      mid = (left + right) / 2
      return mid if timestamps[mid] == target
      
      if timestamps[left] <= timestamps[mid]
        if timestamps[left] <= target && target < timestamps[mid]
          right = mid - 1
        else
          left = mid + 1
        end
      else
        if timestamps[mid] < target && target <= timestamps[right]
          left = mid + 1
        else
          right = mid - 1
        end
      end
    end
    
    -1
  end
end

# Usage
ring = ConfigurationRing.new(10)
ring.add_config(100, {setting: 'a'})
ring.add_config(105, {setting: 'b'})
ring.add_config(110, {setting: 'c'})
ring.find_by_timestamp(105)  # => {setting: 'b'}

Log File Analysis: A log rotation system maintains sorted log entries across multiple rotated files. Finding a specific log entry by timestamp requires searching through the rotated sequence.

class LogRotationSearch
  def initialize(log_files)
    # Each file contains sorted timestamps
    @files = log_files
    @boundaries = extract_boundaries(log_files)
  end
  
  def find_log_entry(timestamp)
    # Boundaries may be rotated if files wrapped around
    file_idx = find_file_with_timestamp(timestamp)
    return nil unless file_idx
    
    search_within_file(@files[file_idx], timestamp)
  end
  
  private
  
  def find_file_with_timestamp(timestamp)
    # @boundaries is rotated sorted array of [min, max] ranges
    left, right = 0, @boundaries.length - 1
    
    while left <= right
      mid = (left + right) / 2
      min_ts, max_ts = @boundaries[mid]
      
      return mid if timestamp >= min_ts && timestamp <= max_ts
      
      # Determine which segment is sorted
      if @boundaries[left][0] <= @boundaries[mid][0]
        # Left sorted
        if @boundaries[left][0] <= timestamp && timestamp < min_ts
          right = mid - 1
        else
          left = mid + 1
        end
      else
        # Right sorted
        if max_ts < timestamp && timestamp <= @boundaries[right][1]
          left = mid + 1
        else
          right = mid - 1
        end
      end
    end
    
    nil
  end
  
  def extract_boundaries(files)
    files.map { |f| [f.first_timestamp, f.last_timestamp] }
  end
  
  def search_within_file(file, timestamp)
    # Standard binary search within single sorted file
    file.entries.bsearch { |entry| entry.timestamp >= timestamp }
  end
end

Scheduling System: A shift scheduling application maintains worker assignments in sorted order by shift start time. When the schedule wraps around midnight, it forms a rotated array. Finding the worker scheduled for a specific time uses rotated search.

class ShiftScheduler
  Shift = Struct.new(:start_time, :worker_id)
  
  def initialize
    @shifts = []
  end
  
  def add_shift(hour, worker_id)
    # Hours 0-23, may wrap around midnight
    @shifts << Shift.new(hour, worker_id)
  end
  
  def rotate_schedule(hours)
    @shifts.rotate!(hours)
  end
  
  def find_worker_at_time(hour)
    idx = search_shift_by_hour(hour)
    idx == -1 ? nil : @shifts[idx].worker_id
  end
  
  private
  
  def search_shift_by_hour(target_hour)
    left, right = 0, @shifts.length - 1
    
    while left <= right
      mid = (left + right) / 2
      mid_hour = @shifts[mid].start_time
      
      return mid if mid_hour == target_hour
      
      left_hour = @shifts[left].start_time
      right_hour = @shifts[right].start_time
      
      if left_hour <= mid_hour
        # Left sorted
        if left_hour <= target_hour && target_hour < mid_hour
          right = mid - 1
        else
          left = mid + 1
        end
      else
        # Right sorted
        if mid_hour < target_hour && target_hour <= right_hour
          left = mid + 1
        else
          right = mid - 1
        end
      end
    end
    
    -1
  end
end

# Usage
scheduler = ShiftScheduler.new
(0..23).each { |hour| scheduler.add_shift(hour, "worker_#{hour}") }
scheduler.rotate_schedule(6)  # Rotate to start at 6am
scheduler.find_worker_at_time(8)  # => "worker_8"

Priority Queue with Rotation: A specialized priority queue implementation uses a rotated sorted array to maintain elements. Rotation occurs when the queue wraps around after dequeuing operations.

class RotatingPriorityQueue
  def initialize(capacity)
    @capacity = capacity
    @items = []
    @priorities = []
    @head = 0
  end
  
  def enqueue(item, priority)
    insert_position = find_insert_position(priority)
    @priorities.insert(insert_position, priority)
    @items.insert(insert_position, item)
  end
  
  def dequeue
    return nil if @items.empty?
    
    item = @items.delete_at(@head)
    @priorities.delete_at(@head)
    @head = (@head + 1) % [@items.length, @capacity].min if @items.any?
    item
  end
  
  def contains_priority?(priority)
    idx = search_rotated(@priorities, priority)
    idx != -1
  end
  
  private
  
  def find_insert_position(priority)
    # Binary search for insertion point in rotated array
    return 0 if @priorities.empty?
    
    left, right = 0, @priorities.length - 1
    result = @priorities.length
    
    while left <= right
      mid = (left + right) / 2
      
      if @priorities[left] <= @priorities[mid]
        if priority < @priorities[mid]
          result = mid
          right = mid - 1
        else
          left = mid + 1
        end
      else
        if priority > @priorities[mid]
          left = mid + 1
        else
          result = mid
          right = mid - 1
        end
      end
    end
    
    result
  end
  
  def search_rotated(arr, target)
    # Standard rotated array search
    left, right = 0, arr.length - 1
    
    while left <= right
      mid = (left + right) / 2
      return mid if arr[mid] == target
      
      if arr[left] <= arr[mid]
        if arr[left] <= target && target < arr[mid]
          right = mid - 1
        else
          left = mid + 1
        end
      else
        if arr[mid] < target && target <= arr[right]
          left = mid + 1
        else
          right = mid - 1
        end
      end
    end
    
    -1
  end
end

Common Patterns

Two-Pointer Segment Identification: The most common pattern maintains left and right pointers while identifying which half remains sorted. After calculating the midpoint, compare array[left] with array[mid] to determine segment order. This pattern handles any rotation point location.

def identify_sorted_segment_pattern(nums)
  left, right = 0, nums.length - 1
  results = []
  
  while left <= right
    mid = (left + right) / 2
    
    if nums[left] <= nums[mid]
      results << {segment: :left, range: [left, mid], sorted: true}
      results << {segment: :right, range: [mid + 1, right], sorted: false}
    else
      results << {segment: :left, range: [left, mid], sorted: false}
      results << {segment: :right, range: [mid + 1, right], sorted: true}
    end
    
    break  # Demo single iteration
  end
  
  results
end

Range Boundary Checking: After identifying the sorted segment, verify whether the target falls within its value range. This pattern combines position-based (index) and value-based (array element) comparisons.

def range_check_pattern(nums, target, left, mid, right)
  if nums[left] <= nums[mid]
    # Left segment sorted
    in_left_range = nums[left] <= target && target < nums[mid]
    {
      sorted_segment: :left,
      target_in_sorted: in_left_range,
      action: in_left_range ? "search left" : "search right"
    }
  else
    # Right segment sorted
    in_right_range = nums[mid] < target && target <= nums[right]
    {
      sorted_segment: :right,
      target_in_sorted: in_right_range,
      action: in_right_range ? "search right" : "search left"
    }
  end
end

Iterative vs Recursive Patterns: Iterative implementations use a while loop with explicit pointer updates. Recursive implementations pass updated bounds as parameters. Both achieve the same logic but differ in space complexity and stack management.

# Iterative pattern
def iterative_pattern(nums, target)
  left, right = 0, nums.length - 1
  
  while left <= right
    mid = (left + right) / 2
    return mid if nums[mid] == target
    
    # Update pointers based on logic
    if condition
      right = mid - 1
    else
      left = mid + 1
    end
  end
  
  -1
end

# Recursive pattern
def recursive_pattern(nums, target, left = 0, right = nums.length - 1)
  return -1 if left > right
  
  mid = (left + right) / 2
  return mid if nums[mid] == target
  
  # Recurse with updated bounds
  condition ? 
    recursive_pattern(nums, target, left, mid - 1) :
    recursive_pattern(nums, target, mid + 1, right)
end

Minimum Finding Pattern: Finding the rotation point (minimum element) uses similar logic but searches for the discontinuity rather than a specific target. This pattern checks if nums[mid] > nums[right] to determine which side contains the minimum.

def find_rotation_point(nums)
  left, right = 0, nums.length - 1
  
  while left < right
    mid = (left + right) / 2
    
    # Minimum is in right half
    if nums[mid] > nums[right]
      left = mid + 1
    else
      # Minimum is in left half or is mid
      right = mid
    end
  end
  
  left  # Index of minimum element (rotation point)
end

arr = [4, 5, 6, 7, 0, 1, 2]
rotation_point = find_rotation_point(arr)
# => 4 (index of element 0)

Duplicate Squeezing Pattern: When duplicates prevent segment identification, incrementally move both pointers inward. This pattern sacrifices logarithmic performance in worst case but handles all duplicate configurations.

def duplicate_squeeze_pattern(nums, target)
  left, right = 0, nums.length - 1
  
  while left <= right
    mid = (left + right) / 2
    return mid if nums[mid] == target
    
    # Cannot determine sorted segment
    if nums[left] == nums[mid] && nums[mid] == nums[right]
      # Squeeze from both ends
      left += 1
      right -= 1
      next
    end
    
    # Continue with normal logic
    # ...
  end
  
  -1
end

Binary Search Combination Pattern: Some problems require first finding the rotation point, then performing standard binary search on the correct segment. This pattern trades a single complex search for two simpler searches.

def two_phase_search(nums, target)
  # Phase 1: Find rotation point
  rotation = find_rotation_point(nums)
  
  # Phase 2: Standard binary search on correct segment
  if target >= nums[rotation] && target <= nums[-1]
    # Search right segment
    nums[rotation..-1].bsearch_index { |x| x >= target }&.then { |i| i + rotation }
  else
    # Search left segment
    nums[0...rotation].bsearch_index { |x| x >= target }
  end || -1
end

Reference

Algorithm Comparison

Key Decision Points

Search Logic Flow

Common Edge Cases

Complexity Analysis

Ruby-Specific Methods

Rotation Point Properties