Problem Submissions Solution
Search In Rotated Sorted Array
Difficulty: Medium
Acceptance: 37.64%
Points: 30.00
Given a sorted (in ascending order) and rotated array **arr** of distinct elements which may be rotated at some point and given an element key, the task is to find the index of the given element **key** in the array arr. The whole array arr is given as the range to search. Rotation shifts elements of the array by a certain number of positions, with elements that fall off one end reappearing at the other end. **Note:** 0-based indexing is followed & returns -1 if the key is not present.
Examples:
Expected Time Complexity: O(log n)
Expected Space Complexity: O(1)
Constraints:
- 1 <= arr.size() <= 10^6
- 0 <= arr[i] <= 10^6
- 1 <= key <= 10^5
Companies:
Amazon Microsoft Adobe Google Intuit + 3 more
Topics:
Array Searching Algorithms
