Last Updated: 3 Feb, 2023

Search In A Rotated Sorted Array II

Easy

Asked in companies

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.

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.

Approaches

01 Approach

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’)

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

02 Approach

Approach:

We can break a rotated sorted array into two parts so that both are sorted. Example - [4, 6, 8, 9, 1, 3, 4] can be divided into two parts [4, 6, 8, 9] and [1, 3, 4].
Since we have two sorted arrays, we can apply a modified binary search on the array.
Initialize two variables, ‘low’ with 0 and ‘high’ with ‘N’-1.
We will apply binary search with the following conditions:
- If the element at ‘mid’ is equal to the ‘key’, we return True.
- Else if the element at ‘mid’ is greater than the element at ‘high’, then the first half is sorted.
  - If the ‘key’ lies between the element at ‘low’ and the element at ‘mid’, we will search in the left half. Else we search in the right half.
- Else if the element at ‘mid’ is lesser than the element at ‘high’, then the second half is sorted.
  - If the ‘key’ lies between the element at ‘mid’ and the element at ‘high’, we will search in the right half. Else we search in the left half.
- Else we will decrease the ‘high’ value as we encounter a case with duplicate elements like [4, 1, 2, 4, 4, 4, 4], where the ‘mid’ element is equal to the ‘high’ element.
If the ‘key’ is not found, we return False.

Algorithm:

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

Int ‘N’ = ‘A’.length()
Int ‘low’=0, ‘high’ = ‘N’-1
While ‘low’ <= ‘high’:
- Int ’mid’ = (‘low’+’high’)/2
- If ‘A[mid]’ == ‘key’:
  - Return True
- If ‘A[mid]’ > ‘A[high]’:
  - If ‘A[low]’ <= ‘key’ and ‘key’< ‘A[mid]’:
    - ‘high’ = ‘mid’-1
  - Else:
    - ‘low’ = ‘mid’+1
- Else If ‘A[mid]’ < ‘A[high]’:
  - If ‘A[mid]’ < ‘key’ and ‘key’<= ‘A[high]’:
    - ‘low’ = ‘mid’+1
  - Else:
    - ‘high’ = ‘mid’-1
- Else:
  - ‘high’ = ‘high’ - 1
Return False

Similar problems

Element Count in Ranges

Posted: 9 Oct, 2025

First Digit One

Posted: 14 Oct, 2025

Minimize Maximum Adjacent Distance

Posted: 3 Nov, 2025

Sorted Doubly Linked List to Balanced BST

Posted: 3 Nov, 2025

Minimized Maximum of Products Distributed to Any Store

Posted: 22 Feb, 2026