Algorithm to find best insert position in sorted array
Posted: 30 Oct, 2020
You are given a sorted array 'A' of length 'N' with distinct integers and a target integer 'M'. You need to return the position of 'M' if it existed in the array 'A'. If it already exists in 'A', return that position. (0-based indexing)
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)
1) The given array has distinct integers. 2) The given array may be empty.
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.
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.
You do not need to print anything, it has already been taken care of. Just implement the given function.
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).
Lexicographic Permutation Rank
Posted: 13 Jul, 2021
Zero Pair Sum
Posted: 22 Jul, 2021
Longest Common Prefix
Posted: 24 Jul, 2021
Implement a Queue
Posted: 27 Jul, 2021
Remove K Corner Elements
Posted: 31 Jul, 2021