binary-search · Problem 3 of 3
Search in Rotated Sorted Array
Amazon
Google
Meta
Microsoft
AppleThere is an integer array nums sorted in ascending order (with distinct values). Prior to being passed to your function, nums is possibly rotated at an unknown pivot index.
Given the array nums and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.
You must write an algorithm with O(log n) runtime complexity.
search([4, 5, 6, 7, 0, 1, 2], 0) -> 4
search([4, 5, 6, 7, 0, 1, 2], 3) -> -1
search([1], 0) -> -1Your solution
Runs your code and animates it without grading anything. Change the input to see what it does on a case the tests do not cover.
Tests
5 cases, 1 hidden| call | type | expected | result |
|---|---|---|---|
| search([4,5,6,7,0,1,2], 0) | target in right sorted half | 4 | — |
| search([4,5,6,7,0,1,2], 3) | target not present | -1 | — |
| search([1], 0) | single element not found | -1 | — |
| search([1], 1) | single element found | 0 | — |
| withheld | hidden | withheld | — |
Hidden cases run too — their inputs aren't listed here, so aim for a general solution rather than one fitted to the cases above.
Complexity
- target time
- O(log n)
- target space
- O(1)
Halves the search space at each iteration using modified binary search boundaries.
Hints
Stuck? Hints open one at a time, each giving a little more away.
3 hints left