Coding

Search in rotated sorted array-I

Asked at

Expedia

Oracle

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The 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) {

    }
}

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

At every iteration, at least one half of a rotated strictly increasing array is sorted. Compute mid; if it equals target, return it. If nums[low] is at most nums[mid], the left half is sorted. Check whether target lies in the inclusive-low, exclusive-mid range; if yes move high left, otherwise move low right. If the left half is not sorted, the right half is; check its range symmetrically. Distinct values make the sorted-half test decisive. Keep the invariant that any possible target remains within low through high, and return minus one only once that interval is empty. Each iteration discards half the interval, so complexity is O(log n) time and O(1) space. Do not separately find the pivot unless asked; that adds moving parts without improving the asymptotics.

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

Hiring now

Expedia has 109 open roles right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Software Development Engineer III - Platform Productivity Tools
India - Gurgaon
Sr Manager, Software Engineering
Austin Domain 11 - HomeAway
Software Development Engineer II
India - Gurgaon

Or practice this question first

Next question