@arunvishwanathan88 said in Java solution, Binary Search:

@shuoshuo70 @q252558242 I'll try to explain about the binary search used here.

Here the binary search is used in a smart way beyond what we would normally see in a text book for searching.

If you have understood the code until binary search, you might have observed that the solution sorts the array and then finds the minimum and maximum difference.

Binary search is then performed in two nested parts. First we start on the SORTED array but using values of low and high of the differences we calculated earlier. So we start with mid as (low+high)/2.

In each step of this binary search, another binary search is performed on the SORTED array (the countPairs() method) to find how many pairs in the sorted array have difference less than or equal to the mid.( the upper bound function implementation in the solution with the loop around it).

If the number of pairs less than k, we know that we are not looking at the kth smallest difference and we can bump up the low and check again.

if the number of pairs is greater than k, we know we have overshot and we could lower the high and check again. It seems to me that the solution is reducing the number of comparisons in binary search by checking for <k only. But I think when we find number of pairs =k we return the smallest difference seen so far.

I am not sure how to analyse the run time complexity. I see a binary search the calls a function over a loop of binary searches.

I am pretty new to coding or rusty I would say. The solution went over my head.

I was trying to see if I could generate all pairs, put the difference in a max heap of size k and pick the top. But I could not get it to work.

Great explaination, thanks!