8

# Algorithm to find best insert position in sorted array

Difficulty: EASY
Contributed By
Sounak Majumder
Avg. time to solve
10 min
Success Rate
85%

Problem Statement

#### For example:

``````If the given array 'A' is: [1, 2, 4, 7] and M = 6. We insert M = 6 in the array and get 'A' as: [1, 2, 4, 6, 7]. The position of 6 is 3 (according to 0-based indexing)
``````
##### Note:
``````1) The given array has distinct integers.

2) The given array may be empty.
``````
##### Input Format:
``````The first line of input contains a single integer 'T', representing the number of test cases or queries to be run.

Then the 'T' test cases follow.

The first line of each test case contains two space-separated integers 'N' and 'M', representing the length of the array and the target integer.

The second line of each test case contains 'N' space-separated integers, Ai representing the given array.
``````
##### Output Format:
``````For each test case, print a single line containing a single integer denoting the position of 'M' in the final array, on a new line.

The output of each test case will be printed 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
0 ≤ N ≤ 10 ^ 5
1 ≤ M ≤ 10 ^ 9
1 ≤ Ai ≤ 10 ^ 9

Where 'T' is the number of test cases and 'Ai' is the array element at index 'i'.

Time Limit: 1 sec.
``````
``````Try to solve the problem in O(log N).
``````
##### Sample Input 1:
``````2
4 6
1 2 4 7
4 9
1 2 4 7
``````
##### Sample Output 1:
``````3
4
``````
##### Explanation of Input 1:
``````The first test case is already explained in the problem statement.

The second test case, the given array 'A' is: [1, 2, 4, 7] and M = 9. We insert M=9 in the array and get 'A' as: [1, 2, 4, 6, 9]. The position of 9 is 4 (according to 0-based indexing)
``````
##### Sample Input 2:
``````2
3 1
2 5 7
3 5
2 5 7
``````
##### Sample Output 2
``````0
1
``````
##### Explanation of Input 2:
``````The first test case, the given array 'A' is: [2, 5, 7] and M = 1. We insert M = 1 in the array and get 'A' as: [1, 2, 5, 7]. The position of 1 is 0 (according to 0-based indexing)

The second test case, the given array 'A' is: [2, 5, 7] and M = 5. We insert M = 5 in the array and get 'A' as: [2, 5, 7].(since the array can have only distinct integers. The position of 5 is 1 (according to 0-based indexing)
``````
Console