CA 20 - Search in Rotated Sorted Array

Problem Statement

There is an integer array nums sorted in ascending order (with distinct values).

Before being passed to your function, nums is possibly rotated at some pivot index such that the resulting array looks like:
[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]

For example:
[0,1,2,4,5,6,7] rotated by 3 → [4,5,6,7,0,1,2]

Given the rotated array nums and an integer target, return the index of target if it exists, otherwise return -1.

You must write an algorithm with O(log n) runtime complexity.

Examples:

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

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Input: nums = [1], target = 0
Output: -1

My Goal

For this problem, my goal was to:

Understand how rotated arrays behave
Apply binary search in a modified way
Maintain O(log n) complexity
Avoid linear search

Solution

I used a modified Binary Search to handle the rotation.

Idea:

In every step, one half of the array is always sorted
Check which half is sorted:
If left half is sorted:
Check if target lies there
Else right half is sorted:
Check if target lies there
Narrow down the search accordingly

Solution Code (Python)

def search(a, t):
    l = 0
    h = len(a) - 1

    while l <= h:
        m = (l + h) // 2

        if a[m] == t:
            return m

        # left half sorted
        if a[l] <= a[m]:
            if a[l] <= t < a[m]:
                h = m - 1
            else:
                l = m + 1
        else:
            # right half sorted
            if a[m] < t <= a[h]:
                l = m + 1
            else:
                h = m - 1

    return -1


a = [4, 5, 6, 7, 0, 1, 2]
t = 0

print(search(a, t))

Explanation

Find middle element
Determine which side is sorted
Check if target lies in that range
Adjust search space accordingly