Relevant

Given an array nums, sorted in ascending order and left rotated at an unknown index k (1 <= k < nums.length), and an integer target, return the index of target if it is in nums, or -1 otherwise.

You must write an algorithm with O(log2n) runtime complexity.

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Example 3:

Input: nums = [1], target = 0
Output: -1

Playground: Leetcode 33

Key Observations

For an array rotated at an unknown index k (1 <= k < nums.length), at least one half of the array will always be sorted in ascending order.

Suitable Approach - Binary Search

Use binary search to repeatedly eliminate the half that cannot contain the target until the target is found or no elements remain to be explored.

Algorithm

1. Initialize two pointers, "start" and "end", to mark the subarray under consideration.

2. Keep performing the below operations while "start" <= "end", i.e., atleast one element exist 
   in the current subarray.
    3. Find the "middle" index of the current subarray.

    4. If "nums[middle]" (middle element of the current subarray) == "target", return the 
       "middle" index.

    5. If "nums[start]" (first element of the current subarray) <= "nums[middle]", the 
       left half of the subarray is sorted.
        6. If "target" < "nums[start]" or "target" > "nums[middle]", the "target" element must 
           lie exist in the right half. Move "start" to "middle + 1".
        7. Otherwise, the "target" lies in the left half. Move "end" to "middle - 1". 

    8. Otherwise if "nums[start]" > "nums[middle]", the right half is sorted.
        9. If "target" < "nums[middle]" element or "target" > "nums[end]" (last element of the 
           current subarray), the "target" must lie in the left half. Move "end" to "middle - 1".
        10. Otherwise, the target lies in the right half. Move "start" to "middle + 1".

11. If the "target" is not found, return -1.

Implementation

Sample inputs

1public int search(int[] nums, int target) {

3 // 1. Initialize two pointers, start and end, to mark the subarray under consideration.

4 int start = 0, end = nums.length - 1;

6 // 2. Keep performing the below operations while atleast one element exist in the current subarray.

7 while (start <= end) {

9 // 3. Find the middle index of the current subarray.

10 int middle = (start + end) / 2;

12 // 4. If the middle element of the current subarray == target element, return the middle index.

13 if (nums[middle] == target) {

14 return middle;

15 }

17 // 5. If the first element of the current subarray <= middle element, the left half

18 // of the subarray is sorted.

19 if (nums[start] <= nums[middle]) {

21 // 6. If target element doesn't lie in the left half, move start pointer to (middle + 1).

22 if (target < nums[start] || target > nums[middle]) {

23 start = middle + 1;

24 } else { // 7. Otherwise, the target element can lie in the left half. Move end pointer to (middle - 1).

25 end = middle - 1;

26 }

29 } else { // 8. Otherwise, the right half is sorted.

31 // 9. If the target element doesn't lie in the right half, move end pointer to (middle - 1).

32 if (target < nums[middle] || target > nums[end]) {

33 end = middle - 1;

34 } else { // 10. Otherwise, the target element can lie in the right half. Move start pointer to (middle + 1).

35 start = middle + 1;

36 }

38 }

40 }

42 // 11. If the target element is not found, return -1.

43 return -1;

45}

nums

S start·M middle·E end

sorted halfother halfdiscarded

Current subarray—

nums[start..end]

target = 0

start = —

middle = —

end = —

nums[start] = —

nums[middle] = —

nums[end] = —

Returned index

—

Ready

Press Play or Step. Highlighted lines, including the comments, are the ones executing.

0/17

Time Complexity

In each iteration, we calculate the middle index, determine which half of the subarray is sorted and, based on the target's value, eliminare one half of the subarray. Since each of these operation takes constant time, O(1), the time complexity is primarily dependent on the number of iterations.

The search space reduces by half in every iteration. The number of remaining element after each iteration is:

-> Initially: n
-> After 1 iteration: n/2
-> After 2 iterations: n/(2^2)
-> After 3 iterations: n/(2^3)
   .
   .
   .
-> After k iterations: n/(2^k)

In the worst case, i.e., when the target element is not found, the search continuous until one element exists. Therefore:

-> n / (2^k) = 1
-> n = 2^k

Taking logarithm base 2 on both sides:
-> log2(n) = k

Since, the number of iterations is proportional to log2(n), the overall time complexity is O(log2(n)).

Space Complexity

The algorithm only uses a constant amount of extra space to store variables as start, end and middle.

Since we are not using any additional data structures, the overall space complexity is O(1).