Last Updated: 27 Feb, 2021

Ninja and Infinite Size Array

Easy

Asked in companies

Solve now

Problem statement

Ninja has been given an array/list ‘ARR’ of unknown size and an element ‘TARGET.’ The ‘ARR’ is sorted in ascending order and all the elements of the ‘ARR’ are different. However, the size of the array is unknown to you. So Ninja can only access the 'ARR' using an interface ‘readValueAtIndex’. If you are trying to access a value from the index not present in the ‘ARR,’ you get output ‘10 ^ 9 + 7’.Ninja has to find that the position of the element ‘TARGET’ if it is present in the ‘ARR’.

For example:

Let ‘ARR’ = {2 4 7 10}.

If you want to know that what is the value at the 0-index in ‘ARR’, use ‘readValueAtIndex(0)’. Then the output is 2.

Let’s assume that you are trying to get the value at the 10’th index so, use ‘readValueAtIndex(10)’. Then the output is ‘10 ^ 9 + 7’. Because you are trying to access an index that is greater than the size of ‘ARR’.

Note: If the element ‘TARGET’ is not present in the ‘ARR’ then return -1.

Input Format

The first line of input contains an integer ‘T’ which denotes the number of test cases. 

The first line of each test case contains a space-separated integer ‘N’ and ‘TARGET’, which represents the size of ‘ARR1’ and an element to be searched.

The next lines of each test case contain ‘N’ space-separated integers which represent the elements of ‘ARR1’.

Output Format :

For each test case, return the position of the element ‘TARGET’ if it is present in the ‘ARR’ otherwise return -1.

Output for each test case should be in a separate line.

Note:

You don't need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= ‘T’ <= 100
1 <= ‘N’ <= 5000
1 <= ‘ARR1[i]’, ‘TARGET’ <= 100000

Where ‘ARR1[i]’ the element of the array 'ARR'.

Time Limit: 1 sec

Solve now

Approaches

01 Approach

As we know, all elements of ‘ARR’ are different. So, we can simply iterate through the ‘ARR’, and if ‘readValueAtIndex(i)’ equal to the ‘TARGET’. Then we return this position. If while traversing through the ‘ARR’ if we reach at the end of the ‘ARR’ then return -1.

The steps are as follows:

We run a loop for ‘i ’= 0 to ‘readValueAtIndex(i) != 10^9+7:
- If ‘readValueAtIndex(i)’ == ‘TARGET’:
  - Return ‘i’.
Return -1.

Solve now

02 Approach

As we know, all elements are present in ‘ARR’ are in sorted order. As we know end index ‘Ei’ of ‘ARR’ is unknown. So first, we try to find the ‘Ei’. We initialize ‘Ei’ to 1, then run a loop while ‘readValueAtIndex(Ei)’ is less than ‘TARGET, and every time we change ‘Ei’ to ‘Ei* 2’. Now, we know if the given element is present, then it is greater than ‘Ei’ / 2 and less than ‘Ei’. So we initialize ‘Si’ to ‘Ei’ / 2 and ‘Ei’ to ‘Ei’ and then apply binary search.

The steps are as follows:

We declare a variable ‘Ei’ and initialize it with 1.
We run a loop while ‘readValueAtIndex(Ei)’ < ‘TARGET’:
- ‘Ei’ = ‘Ei’ * 2.
We declare a variable ‘Si’ and initialize it with ‘Ei/2’.
We run a loop while ‘Si’ <= ‘Ei’:
- ‘MID’ = (‘Si’ + ‘Ei’)/2
- If ‘readValueAtIndex(MID)’ == ‘TARGET’:
  - Return ‘MID’
- Else if ‘readValueAtIndex(mid)’ > ‘TARGET’:
  - ‘Ei’ = ‘MID’ - 1.
- Else
  - ‘Si’ = ‘MID’ + 1.
Return -1.

Solve now