Search in rotated sorted array-I
Expedia
OracleThe problem
Given an integer array nums, sorted in ascending order (with distinct values) and a target value k. The array is rotated at some pivot point that is unknown. Find the index at which k is present and if k is not present return -1.
Input : nums = [4, 5, 6, 7, 0, 1, 2], k = 0 Output: 4 Explanation: Here, the target is 0. We can see that 0 is present in the given rotated sorted array, nums. Thus, we get output as 4, which is the index at which 0 is present in the array.
Input: nums = [4, 5, 6, 7, 0, 1, 2], k = 3 Output: -1 Explanation: Here, the target is 3. Since 3 is not present in the given rotated sorted array. Thus, we get the output as -1.
Input: nums = [4, 5, 6, 7, 0, 1, 2], k = 5
- 1 <= nums.length <= 104
- -104 <= nums[i] <= 104
- All values of nums are unique.
- nums is an ascending array that is possibly rotated.
- -104 <= k <= 104
cpp
class Solution {
public:
int search(vector<int> &nums, int k) {
}
};java
class Solution {
public int search(int[] nums, int k) {
}
}python
class Solution:
def search(self, nums, k):javascript
class Solution {
search(nums, k) {
}
}csharp
public class Solution {
public int Search(int[] nums, int k) {
}
}go
func search(nums []int, k int) int {
}Stuck? Show a way to structure it+
- 01Compare middle with target.
- 02Determine whether the left half is sorted.
- 03Search left when target lies in that sorted range.
- 04Otherwise search right.
- 05Return minus one once the interval is empty.
Reference answer
Then expect these follow-ups
How do duplicates change the sorted-half test?
Tests: constraint adaptation
How would you return an insertion position if target is absent?
Tests: implementation extension
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question