✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-125

Searching in Rotated Sorted Arrays

Searching in a rotated sorted array requires identifying which portion of the array remains correctly sorted and determining whether the target can exist within that portion. A modified binary search can solve the distinct-element version in O(log n) time.

Explanation

Overview

A rotated sorted array is an array created by moving some leading elements of a sorted array to the end while preserving the relative order of the elements. Searching in such an array requires adapting binary search because the entire array is no longer globally sorted.

Purpose

The purpose of this technique is to locate a target efficiently without first restoring the original sorted order.

Key concepts

name: Core idea; description: The central focus of searching in rotated sorted arrays is the capability described here: Searching in a rotated sorted array requires identifying which portion of the array remains correctly sorted and determining whether the target can exist within that portion. A modified binary search can solve the distinct-element version in O(log n) time.; name: Problem context; description: Searching in Rotated Sorted Arrays is relevant when a computational task requires the behavior or capability described by this topic.; name: Correct use; description: Before using searching in rotated sorted arrays, check its assumptions, input requirements, expected output, and resource constraints.

Space complexity

O(1) auxiliary space for the standard iterative implementation.

Example

Consider the rotated array [15, 18, 22, 2, 5, 8, 11] and target 5. The algorithm identifies the sorted portion of the current interval, determines which portion can contain 5, and continues narrowing the search until the target is found at index 4.

Pseudocode

SEARCH_ROTATED(A, target):
low = 0
high = length(A) - 1
while low <= high:
mid = low + (high - low) // 2
if A[mid] == target:
return mid
if A[low] <= A[mid]:
if A[low] <= target and target < A[mid]:
high = mid - 1
else:
low = mid + 1
else:
if A[mid] < target and target <= A[high]:
low = mid + 1
else:
high = mid - 1
return -1

Advantages

Avoids sorting the array again before searching.; Achieves O(log n) time when elements are distinct.; Uses constant auxiliary space in the iterative form.; Takes advantage of the sorted structure that remains after rotation.

Example or application

Consider the rotated array [15, 18, 22, 2, 5, 8, 11] and target 5. The algorithm identifies the sorted portion of the current interval, determines which portion can contain 5, and continues narrowing the search until the target is found at index 4.

Definition

A rotated sorted array is an array created by moving some leading elements of a sorted array to the end while preserving the relative order of the elements. Searching in such an array requires adapting binary search because the entire array is no longer globally sorted.

Purpose

The purpose of this technique is to locate a target efficiently without first restoring the original sorted order.

Array Rotation

A rotation changes the starting position of a sorted sequence. For example, rotating [2, 5, 8, 12, 17, 21, 26] can produce [17, 21, 26, 2, 5, 8, 12].

Structural Property

Although the complete array may not be sorted, at least one half of the current interval is normally sorted when all elements are distinct. This property allows a modified binary search to eliminate half of the interval.

Working Principle

The algorithm examines the middle element and determines which half is sorted. It then checks whether the target falls within the value range of that sorted half. If it does, the search continues there; otherwise, it continues in the other half.

Algorithm Steps

  • Initialize low and high to the first and last valid indices.

  • Calculate the middle index.

  • If the middle element matches the target, return its index.

  • Determine whether the left half is sorted by comparing its boundary values.

  • If the left half is sorted, check whether the target lies within its value range.

  • If it does, move the upper boundary to mid - 1; otherwise, move the lower boundary to mid + 1.

  • If the right half is sorted, check whether the target lies within its value range.

  • Choose the appropriate half and repeat until the target is found or the interval becomes empty.

Pseudocode

SEARCH_ROTATED(A, target):
low = 0
high = length(A) - 1
while low <= high:
mid = low + (high - low) // 2
if A[mid] == target:
return mid
if A[low] <= A[mid]:
if A[low] <= target and target < A[mid]:
high = mid - 1
else:
low = mid + 1
else:
if A[mid] < target and target <= A[high]:
low = mid + 1
else:
high = mid - 1
return -1

Best Case

O(1) time when the target is found at the first middle position examined.

Average Case

O(log n) time for the standard distinct-element version because each iteration can eliminate approximately half of the remaining interval.

Worst Case Distinct Elements

O(log n) time when all elements are distinct and the algorithm can reliably identify a sorted half at each step.

Worst Case With Duplicates

O(n) time may be required when duplicates make it impossible to determine which half is sorted. For example, equal values at the low, middle, and high positions can provide insufficient information to eliminate an entire half.

Space Complexity

O(1) auxiliary space for the standard iterative implementation.

Distinct Element Assumption

The straightforward logarithmic implementation assumes distinct elements. Under this assumption, the sorted half can be identified reliably through boundary comparisons.

Duplicate Handling

When duplicates are allowed, additional conditions may be needed. If A[low], A[mid], and A[high] are equal, the algorithm can shrink the boundaries by moving low forward and high backward, but this may require linear time in the worst case.

Rotation Point

The rotation point is the position where the original ascending sequence was divided and rearranged. It is often associated with the smallest element in the rotated array.

Alternative Approach

Another strategy is to find the rotation point first and then perform ordinary binary search in the appropriate sorted portion. This separates rotation-point detection from target lookup but requires correct boundary selection.

Advantages

  • Avoids sorting the array again before searching.

  • Achieves O(log n) time when elements are distinct.

  • Uses constant auxiliary space in the iterative form.

  • Takes advantage of the sorted structure that remains after rotation.

Limitations

  • The complete array is not globally sorted.

  • The algorithm requires additional logic to identify a sorted half.

  • Duplicates can make the sorted half difficult to identify.

  • Incorrect boundary conditions can cause valid elements to be skipped.

Practical Applications

  • Searching in rotated numerical arrays.

  • Working with cyclically shifted ordered datasets.

  • Looking up values in arrays that have been rotated for storage or processing.

  • Interview and algorithm-design problems involving modified binary search.

Implementation Considerations

The implementation should handle empty arrays, arrays containing one element, arrays that have not been rotated, and targets located near the rotation point. If duplicates are permitted, the implementation must explicitly address ambiguous boundary comparisons.

Common Errors

  • Applying ordinary binary search without accounting for the rotation.

  • Assuming both halves are sorted.

  • Checking the target range with incorrect inclusive or exclusive boundaries.

  • Ignoring the duplicate-element case.

  • Using a midpoint calculation that may overflow in fixed-width integer environments.

Key Takeaway

A rotated sorted array still contains useful sorted sections. Modified binary search uses those sections to eliminate impossible ranges efficiently, achieving O(log n) time for distinct elements while potentially requiring O(n) time when duplicates create ambiguity.

Key Concepts

NameDescription

Core idea

The central focus of searching in rotated sorted arrays is the capability described here: Searching in a rotated sorted array requires identifying which portion of the array remains correctly sorted and determining whether the target can exist within that portion. A modified binary search can solve the distinct-element version in O(log n) time.

Problem context

Searching in Rotated Sorted Arrays is relevant when a computational task requires the behavior or capability described by this topic.

Correct use

Before using searching in rotated sorted arrays, check its assumptions, input requirements, expected output, and resource constraints.

Practice Questions

QuestionAnswer

What is the main purpose of searching in rotated sorted arrays?

Searching in a rotated sorted array requires identifying which portion of the array remains correctly sorted and determining whether the target can exist within that portion. A modified binary search can solve the distinct-element version in O(log n) time.

What should be checked before applying searching in rotated sorted arrays?

For searching in rotated sorted arrays, verify the stated inputs, assumptions, expected result, boundary cases, and time and memory constraints.

How can an implementation of searching in rotated sorted arrays be validated?

Trace a representative searching in rotated sorted arrays case manually, test its boundary conditions, and compare the result with the specification or a trusted baseline.

Learning Objectives

  • Explain the central idea and purpose of searching in rotated sorted arrays.

  • Identify the assumptions, inputs, and conditions relevant to searching in rotated sorted arrays.

  • Evaluate an application of searching in rotated sorted arrays for correctness and practical resource requirements.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Scienexy Computer Science Reference

Suggest a correction or source · More in Algorithms & Data Structures