Last Updated: 20 May, 2021
Treasure Hunt
Easy
Asked in companies
Alex and Rome are playing treasure hunting. Rome has a treasure box that Alex wants to open. Rome has N keys, each of which has a unique key number. She placed the keys in boxes numbered from 1 to N. Alex somehow cheated and came to know the key number that opens the treasure box. But he doesn’t know the box number which contains the key. Alex knows that for any box ‘i’ the key in the ith box has a key number greater than the key numbers of the keys placed in any box j where j<i.
Given a list of key numbers, help Alex find the box number which contains the key. Or report that Rome has not placed the correct key in any of the boxes.
Input Format:
The first line of input contains an integer ‘T’, denoting the number of test cases. Then the test cases follow.
The first line of each test case contains two space-separated integers, ‘N’ and ‘K’, denoting the number of boxes and the correct key number, respectively.
The second line of each test case contains ‘N’ space-separated integers denoting the key numbers in the array ‘key’.
Output Format:
For each test case, Print the box number which contains the correct key or ‘-1’ if the key is not present.
Print the output of each test case in a new line.
Note:
You are not required to print the expected output. It has already been taken care of. Just implement the function.
It is guaranteed that key[i] > key[j] for all i>j.
Constraints:
1<= T <= 10
1 <= N <= 10^4
1 <= K <= 10^9
1 <= key[i] <= 10^9
Where ’T’ is the number of test cases, ‘N’ is the number of boxes, ‘K’ is the correct key number, and 'key[i]' is the key number of the key in the ith box.
Time Limit: 1 sec
Approaches
The idea here is to traverse the entire array ‘key’ linearly and find the box which contains the required key.
The steps are as follows:
- We will initialize a variable ‘answer’ to -1.
- Iterate from i = 0 to N - 1:
- If the current box contains the required key, then update ‘answer’ to the current index.
- We will start from the 1st box and iteratively move to the Nth box.
- If there is no box with the required key, then ‘answer’ is already -1. So, we will return ‘answer’ as the final answer.
As the given array ‘key’ is sorted, the idea is to use binary search instead of linear search. Suppose we have checked the ith box, and it contains a key number smaller than the required key number. Then it is not possible for the required key to be present in the jth box for j<i, since the list is sorted. Thus after checking the ith box, it is beneficial to check only in the range i+1 to N.
Thus, we can divide the array into two parts, check the middle element, and accordingly continue checking in the first half or second half.
The steps are as follows:
- We will initialize two variables, ‘L’ and ‘R’ be the first and last indexes of the array we are working with (0 index based). Initially, L=0 and R=N.
- We will execute a while loop with the condition ‘R’ is greater than or equal to ‘L’.
- We will calculate mid=(L+R)/2.
- First, we compare K with the element at mid. If found equal, we will return mid.
- If not, then we check whether K is greater than the element at mid. If yes, then we will recur to the second part.
- If not, then we will recur to the first part.
- If we get out of the while loop, it means the given key is not present in the array ‘key’. So, we will return -1 as the final answer.
Similar to the binary search approach, we can now divide the list into three parts and check which half may contain the required key.
The steps are as follows:
- We will initialize two variables, ‘L’ and ‘R’ be the first and last indexes of the array we are working with (0 index based). Initially, L=0 and R=N.
- We will execute a while loop with the condition ‘R’ is greater than or equal to ‘L’.
- We will calculate mid1 = L + (R-L)/3 and mid2 = R - (R-L)/3 respectively.
- First, we compare K with the element at mid1. If found equal, we will return mid1.
- If not, then we compare K with the element at mid2. If found equal, we will return mid2.
- If not, then we check whether K is less than the element at mid1. If yes, then we will recur to the first part.
- If not, then we check whether K is greater than the element at mid2. If yes, then we will recur to the third part.
- If not, then we will recur to the second (middle) part.
- If we get out of the while loop, it means the given key is not present in the array ‘key’. So, we will return -1 as the final answer.
Similar problems