Part 6 of 22 in Binary Search  

Find first occurrence of an integer in a sorted list with duplicates by animeshn

Problem statement

Given a sorted list of integers, find the position of first occurrence of a given number in this list in O(log n).

Input

First line of input will contain a positive integer T = number of test cases. Each test case will contain two lines. First line will contain two positive integer N = number of elements in list and K. Next line will contain N space separated integers in increasing order.

Output

For each test case, print on a single line the index of first occurrence of K in the list on 0-based index. Print -1 if you cannot find K in the list.

Sample Input
3
10 4
1 2 4 4 4 4 5 8 9 10
15 7
1 2 3 3 5 6 7 7 7 7 7 8 8 8 8
9 1
-5 -4 -3 -2 -1 0 0 0 1
Sample Output
2
6
8


To try out your code



Sign in

Sign up