A sorted array of distinct integers has been rotated at some unknown pivot: for example [0, 1, 2, 4, 5, 6, 7] might become [4, 5, 6, 7, 0, 1, 2]. Given such an array and a target value, return the index of the target, or -1 if it is not present. Aim for O(log n) time. def search_rotated(nums: List[int], target: int) -> int: pass Input nums, a list of distinct integers, originally sorted ascending then rotated left by some unknown amount (possibly zero). target, the integer to find. Output An integer: the index of target in nums, or -1 if it is absent. Examples search_rotated([4, 5, 6, 7, 0, 1, 2], 0) returns 4. search_rotated([4, 5, 6, 7, 0, 1, 2], 3) returns -1. search_rotated([1], 1) returns 0.

Modified binary search. Plain binary search needs a sorted array, but a rotated array is sorted in two pieces. At each step at least one half (low..mid or mid..high) is properly sorted; we detect it by comparing nums[lo] with nums[mid], then decide whether the target lies within that sorted half's value range and discard the other half. We still halve the search space each iteration, so it is O(log n) time and O(1) space. from typing import List def search_rotated(nums: List[int], target: int) -> int: lo, hi = 0, len(nums) - 1 while lo

Complete Training For Your Trading Interview

Interview Questions Programming Search a Rotated Array

Unlock

Sorry, you don't have access to this interview question. Sign up to practice with our wide range of interview questions or use the filters to find free examples!

Python scratchpad

# Run Python right here in your browser
def two_sum(nums, target):
    seen = {}
    for i, n in enumerate(nums):
        if target - n in seen:
            return [seen[target - n], i]
        seen[n] = i
    return []

print(two_sum([2, 7, 11, 15], 9))  # [0, 1]

Run Python in your browser

Write and execute code — numpy, pandas & scikit-learn included — right on the question page.

My Notes

Notes are saved in this browser only. Sign up to keep them in your account.

Related Questions (16)

Title	Category	Subcategory	Difficulty	Status
All Pairs	Programming	Array and List Processing	Easy	Example
All Permutations	Programming	Array and List Processing	Medium	Unlock
Arithmetic Mean	Programming	Array and List Processing	Hard	Unlock
Binary Search Tree (BST)	Programming	Array and List Processing	Hard	Unlock
Counting Inversions	Programming	Array and List Processing	Hard	Unlock
Crate Loading	Programming	Array and List Processing	Easy	Unlock
Find the Missing Number	Programming	Array and List Processing	Easy	Unlock
Finding the Largest Possible Number	Programming	Array and List Processing	Easy	Unlock
Longest Common Subsequence (LCS)	Programming	Array and List Processing	Medium	Example
Longest Increasing Subsequence	Programming	Array and List Processing	Hard	Unlock
Majority Element	Programming	Array and List Processing	Medium	Unlock
Maximum Subarray Sum	Programming	Array and List Processing	Medium	Unlock
Settling Array	Programming	Array and List Processing	Medium	Unlock
Sorting Without Sort()	Programming	Array and List Processing	Hard	Unlock
Subarray Sum Equals Zero	Programming	Array and List Processing	Medium	Unlock
Sudoku	Programming	Array and List Processing	Hard	Unlock

Discussion

Please log in to see the discussion.

Back to all Questions

The Interview Guide for Quants and Traders

Search a Rotated Array

What do you think of this page?