Problems/Binary Search/Find the Target in a Rotated Sorted Array
Binary Search
medium

Find the Target in a Rotated Sorted Array

The Rotated Array Search problem challenges you to find a target value in a sorted array that has been rotated. Mastering this problem demonstrates your ability to adapt binary search to non-standard scenarios, a key skill for efficient algorithm design.

arraybinary searchdivide and conquersearching

Problem Statement

Given an array of integers that was originally sorted in ascending order, but has been rotated by an unknown number of positions, and a target integer, find the index of the target in the rotated array. If the target is not found in the array, return -1. Assume there are no duplicate values in the array.

Example 1
Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 0
Output: 4
The target value 0 is located at index 4 in the rotated array.
Example 2
Input: nums = [6, 7, 8, 1, 2, 3, 4, 5], target = 6
Output: 0
The target value 6 is located at index 0 in the rotated array.
Constraints
  • -The array will contain unique integers.
  • -The array is sorted before rotation.
  • -The array has been rotated at least once.
  • -The target value is an integer.
  • -The length of the array will be between 1 and 10000.

Brute Force Approach

Imagine you're searching for a specific book on a shelf. The most straightforward approach is to check each book one by one until you find the one you're looking for. This is the brute-force approach: iterate through the entire array and compare each element to the target value.

TimeO(n)
SpaceO(1)

Ready to practice?

Work through this problem with AI coaching and get real-time feedback

Practice This Problem