Search In A Rotated Sorted Array II

Easy
0/40
profile
Contributed by
161 upvotes
Asked in companies
FacebookAmazonThe D. E. Shaw Group

Problem statement

You are given a rotated sorted array 'a' of length 'n' and a 'key'. You need to determine if the 'key' exists in the array 'a'.


The given sorted array is rotated from an unknown index 'x'. Such that after rotation the array became [a[x], a[x+1]...., a[n-1], a[1]..., a[x-1]], (0-based indexing). For example, if the array is [1, 2, 3, 4, 5] and x = 2 then the rotated array will be [3, 4, 5, 1, 2, 3].


Return True if the 'key' is found in 'a'. Otherwise, return False.


Note: Array ‘a’ may contain duplicate elements.


Example:

Input: a = [6, 10, 1, 3, 5], key = 3

Output: True

Explanation: The array 'a' contains the 'key' = 3, so we return True.


Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input contains two integers, 'n' and 'key', separated by a space.
The next line contains 'n' space-separated integers representing the elements of the array 'n'.


Output Format: 
Return a boolean 'true' or 'false' as stated in the problem statement. 'True' is printed for a returned value of 'true' and 'False' otherwise.


Note: 
You don’t need to print anything. Just implement the given function.
Sample Input 1:
7 4
3 4 5 0 0 1 2


Sample Output 1:
True


Explanation Of Sample Input 1:
Input: a = [3, 4, 5, 0, 0, 1, 2], key = 4

Output: True

Explanation: The array 'a' contains the 'key' = 3, so we return True.


Sample Input 2:
6 47
31 44 56 0 10 13


Sample Output 2:
False


Expected Time Complexity:
Try to solve this with average time complexity O(log(n)).
Constraints:
1 <= 'n' <= 10^5
0 <= 'a[i]', 'key' <= 10^9
Time Limit: 1 sec
Hint

We can linearly iterate over the array to find the ‘key’.

Approaches (2)
Brute Force

Approach:

 

  • Iterate over the array ‘A’ and return True if ‘A[i]’ == ‘key’ for some ‘i’ from 0 to ‘N’-1.
  • Else return False.

 

Algorithm:

 

Function bool searchInARotatedSortedArrayII( int []‘A’, int ‘key’)

  1. Int ‘N’ = ‘A’.length()
  2. For ‘i’ from 0 to ‘N’-1:
    • If ‘A[i]’ == ‘key’:
      • Return True
  3. Return False.
Time Complexity

O( N ), Where ‘N’ is the array ‘A’ length. 

Iterating over an array of length ‘N’ takes O(N) complexity. Hence, the overall time complexity will be O( N ).

Space Complexity

O( 1 ). 

We are taking O( 1 ) extra space for variables. Hence, the overall space complexity will be O( 1 ).

Code Solution
(100% EXP penalty)
Search In A Rotated Sorted Array II
Full screen
Console