Last Updated: 23 Oct, 2021

Ninja and Sorted List

Moderate

Asked in companies

Solve now

Problem statement

There is a list of N files, and each file has a given file ID. Array ‘ARR’ contains the list of all file IDs.Ninja’s task is to tell whether a file with ID = ‘VAL’ exists in the list or not. So, to answer the query quickly, Ninja sorted the list. But, due to system error, the sorted array got rotated at an unknown pivot. Can you help Ninja with this problem?

You are given a rotated sorted array ‘ARR’ having ‘N’ elements and an integer ‘VAL’. You to check whether ‘VAL’ exists in the given array or not.

For Example

If the ARR is [4,6,9,11,1,2,2] and ‘VAL’ is 4, the answer will be ‘YES’ as 4 exist in ‘ARR’.

Input Format:

The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains two integers, ‘N’ denoting the number of elements in array ‘ARR’ and ‘VAL’ representing the number to be found.

The following line contains ‘N’ values corresponding to elements of ‘ARR’.

Output Format:

For each test case, print ‘YES’ or ‘NO’ whether the ‘VAL’ exists in the array or not.

Print the output of each test case in a separate line.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N <= 10^7.
1 <=ARR[i] <=10^6.
1 <= VAL <= 10^6.

Time limit: 1 sec

Solve now

Approaches

01 Approach

In this approach, we will simply perform a linear search over the array and try to find ‘VAL’. If we find ‘VAL’ , we will return True otherwise, return False.

Algorithm:

For i in range 0 to ‘N’ -1, do the following:
- If ‘VAL’ is equal to ARR[i]:
  - ‘VAL’ is found.
  - Return True.
Return False.

Solve now

02 Approach

In this approach, we will use a modified binary search over the array. In every step, we will divide the array into two parts. And will decide which part is sorted and move to the half in which ‘VAL’ may lie.

Conditions will be:

1. If ARR[l] <= ARR[mid],the left half is sorted.

i) If ARR[l]<= ‘VAL’ and ARR[mid]>’VAL’. ‘VAL’ may lie in this range. Move to the left half.

ii) Else, Move to the right half.

2. If ARR[mid] <= ARR[r],the right half is sorted.

i) If ARR[mid] <= ‘VAL’ and ARR[r] > ’VAL’. ‘VAL’ may lie in this range. Move to the right half.

ii) Else, Move to the left half.

But, as the array may contain duplicate elements, these conditions do not guarantee that the respective half is sorted.

For example, if the ARR is [3 1 2 3 3 3 3] and mid=3,l=0 and r=6.The condition ARR[l]<=ARR[mid] is satisfied but the left half is not sorted.

So, we have to deal with the duplicate numbers separately as the following:

1. If A[l] == A[mid],increment l to l+1.

2. If A[r] == A[mid],decrement r to r-1.

So, according to all these conditions, we will make a binary search approach, which will return whether ‘VAL’ is present in ‘ARR’ or not.

Algorithm:

Set ‘L’ as 0.
Set ‘R’ as ‘N’ -1.
Set ‘MID’ as (‘L’+’R’)/2.
While ‘L’ <= ‘R’, do the following:
- Set ‘MID’ as (‘L’+’R’)/2.
- If ARR[MID] == ‘VAL’:
  - ‘VAL’ is found.
  - Return True.
- If ARR[L] < ARR[MID].The left half is sorted.
  - If ARR[L] <= ‘VAL’ and ARR[MID]>’VAL’.
    - Move to the left half.
    - Set ‘R’ as ‘MID’ -1.
  - Else:
    - Set ‘L’ as ‘MID’ + 1.
  - Continue.
- If ARR[MID] < ARR[R].The right half is sorted.
  - If ARR[MID] <= ‘VAL’ and ARR[R]>’VAL’.
    - Move to the right half.
    - Set ‘L’ as ‘MID’ + 1.
  - Else:
    - Set ‘R’ as ‘MID’ - 1.
  - Continue.
- If ‘ARR[MID] == ARR[L]:
  - Set ‘L’ as ‘L’+1.
- If ARR[MID] ==ARR[R]:
  - Set ‘R’ as ‘R’ + 1.
If ‘VAL’ is not found yet, it is not present in ‘ARR’.
Return False.

Solve now