DSA Visualizations | Hello Interview

Search in Rotated Sorted Array

DESCRIPTION (credit Leetcode.com)

You are given a sorted array that has been rotated at an unknown pivot point, along with a target value. Develop an algorithm to locate the index of the target value in the array. If the target is not present, return -1. The algorithm should have a time complexity of O(log n).

Note:

The array was originally sorted in ascending order before being rotated.
The rotation could be at any index, including 0 (no rotation).
You may assume there are no duplicate elements in the array.

EXAMPLES

Example 1:
Input:


nums = [4,5,6,7,0,1,2], target = 0

Output: 4 (The index of 0 in the array)

Example 2:

Input:


nums = [4,5,6,7,0,1,2], target = 3

Output: -1 (3 is not in the array)

Run your code to see results here

Explanation

The fact that this question is asking for a O(log n) solution is a hint that we should be using binary search to solve it. If we can iteratively search for our target value in the array while reducing the relevant search space by half in each iteration, then we can achieve the desired time complexity.

So let's first look at an example of a rotated sorted array and see if we can notice anything that will help us do so.

Reducing the Search Space

The visual below shows the same sorted array rotated at different points, including no rotation at all.

If we draw a line down the middle element of each array, this splits the array into two halves. Notice how at least one of the halves is always sorted in ascending order, shown in dark green in the visual.

We'll learn which half to choose when both halves are sorted (like in the first and fourth arrays) in the next step, when we learn how to determine the sorted half.

We'll also mention why the middle element itself is greyed out a little later.

The fact that one half of the array is always sorted is great for our goal, because we can quickly tell if our target falls within the range of that half by comparing the target with its endpoints.

If our target 3 falls within the range of the sorted half, we can confidently discard the other half of the array:

Two examples of where our target = 3 falls within the range of the sorted half of the array, which allows us to discard to other half.

Otherwise, we can discard the sorted half and continue our search in the other half.

So we've accomplished our goal - we used the fact the one half of the array is always sorted to reduce our search space by half.

We can now apply the same logic as above to the half of the array we didn't discard. But first, let's see how to determine which half of the array is sorted.

Determining the Sorted Half

In a regular, unrotated, sorted array, the first element will always be less (or equal to) the middle element. However, this isn't always true for a rotated sorted array.

In a rotated search array, the middle element mid will sometimes be less than the first element left. This happens when the rotation occurs somewhere between left and mid, meaning the right half of the array is sorted.

Notice how in the first array, both halves of the array are actually sorted, as the rotation occurs right at mid. However, we still choose the right half as the sorted half because mid < left.

However, if the middle element mid is greater than the first element left, we know that the left half of the array is sorted, like shown in the 3 examples below.

Algorithm

We now have enough information to visualize our algorithm.

Initialize two pointers left = 0 and right = len(nums) - 1 as the boundaries of our search space.

Now we iteratively try to reduce our search space until its either empty or we find the target.

Initialize pointer mid = (left + right) // 2, and check if nums[mid] == target. If we find the target, we return mid. If it isn't, this removes mid from our search space.

target = 3

Determine which half is sorted: check if nums[left] < nums[mid]. If true, the left half is sorted. If not, the right half is sorted.

In this case, the left half is sorted, so we check if the target is within nums[left] (8) and nums[mid] (16).

3 is not within 8 and 16, so we discard the left half of the array from our search space by updating left = mid + 1. We just reduced our search space in half!

target = 3

Now we repeat the process as above with the updated search space...

Set mid = (left + right) // 2 and check if nums[mid] == target.

target = 3

Check which half is sorted: nums[left] (17) is greater than nums[mid] (1), so the right half is sorted.
Check if the target is within nums[mid] (1) and nums[right] (3). It is, so we update left = mid + 1 to discard the left half of the array.

target = 3

This continues until either we find the target or our search space is empty (left > right).

Solution

def search(nums, target):
    left = 0
    right = len(nums) - 1

    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid

        if nums[left] <= nums[mid]:
            # left half is sorted
            if nums[left] <= target and target < nums[mid]:
                # target is in the left half
                right = mid - 1
            else:
                # target is in the right half
                left = mid + 1
        else:
            # right half is sorted
            if nums[mid] < target and target <= nums[right]:
                # target is in the right half
                left = mid + 1
            else:
                # target is in the left half
                right = mid - 1
    return -1


def search(nums, target):
  left = 0
  right = len(nums) - 1

  while left <= right:
    mid = (left + right) // 2
    if nums[mid] == target:
      return mid
    if nums[left] <= nums[mid]:
      if nums[left] <= target and target < nums[mid]:
        right = mid - 1
      else:
        left = mid + 1
    else:
      if nums[mid] < target and target <= nums[right]:
        left = mid + 1
      else:
        right = mid - 1
  return -1

search for 3 in rotated sorted array

0 / 9

Complexity Analysis

Time Complexity: O(log n). We are reducing the search space by half in each iteration, just like we do in classic binary search.

Space Complexity: O(1). We are using a constant amount of space.

Next: Overview

Your account is free and you can post anonymously if you choose.

Loading comments...

Back to Home

Eliminating Pairs

Overview

Container With Most Water

3-Sum

Triangle Numbers

Pointers as Regions

Move Zeroes

Sort Colors

Trapping Rain Water

Variable-Length

Overview

Longest Substring Without Repeating Characters

Longest Repeating Character Replacement

Fixed-Length

Overview

Maximum Sum of Subarrays of Size K

Max Points You Can Obtain From Cards

Max Sum of Distinct Subarrays Length k

Overview

Can Attend Meetings

Insert Interval

Non-Overlapping Intervals

Merge Intervals

Employee Free Time

Overview

Valid Parentheses

Decode String

Longest Valid Parentheses

Monotonic Stack

Overview

Daily Temperatures

Largest Rectangle in Histogram

Overview

Linked List Cycle

Palindrome Linked List

Remove Nth Node From End of List

Reorder List

Swap Nodes in Pairs

Overview

Apple Harvest (Koko Eating Bananas)

Search in Rotated Sorted Array

Overview

Kth Largest Element in an Array

K Closest Points to Origin

Find K Closest Elements

Merge K Sorted Lists

Introduction

Binary Trees

Overview

Level Order Sum

Rightmost Node

Zigzag Level Order

Maximum Width of Binary Tree

Graphs

Overview

Minimum Knight Moves

Rotting Oranges

01-Matrix

Bus Routes

Overview

Word Search

Solution Space Trees

Subsets

Generate Parentheses

Combination Sum

Topological Sort

Overview

Course Schedule

Course Schedule II

Fundamentals

Solving a Question with Dynamic Programming

Counting Bits

Decode Ways

Maximal Square

Unique Paths

Longest Increasing Subsequence

Word Break

Maximum Profit in Job Scheduling

Overview

Best Time to Buy and Sell Stock

Gas Station

Jump Game

Overview

Implement Trie Methods

Prefix Matching

Overview

Count Vowels in Substrings

Subarray Sum Equals K

Spiral Matrix

Rotate Image

Set Matrix Zeroes

Apple Harvest (Koko Eating Bananas)

Heap: Overview

Search in Rotated Sorted Array

DESCRIPTION (credit Leetcode.com)

Note:

The array was originally sorted in ascending order before being rotated.
The rotation could be at any index, including 0 (no rotation).
You may assume there are no duplicate elements in the array.

EXAMPLES

Example 1:
Input:


nums = [4,5,6,7,0,1,2], target = 0

Output: 4 (The index of 0 in the array)

Example 2:

Input:


nums = [4,5,6,7,0,1,2], target = 3