ji qi’s blog is building…

Finding a value in a sorted sequence->Based on the comparison and because the sequence is sorted, it can then eliminate half of the search space.

1. Find K-th Smallest Pair Distance
   • stupid method: diff in array -> diff add to priority queue, output k-th element
   • problem: memory limited: collections only can hold MAX_VLAUE data
   • solution: why sorted, the 0 smallest distance, and [length -1] - [0] is largest distance
     • range: 0 ~ [length-1]-[0]
     • thought: each time compare and reduce item number to half of before
   • how: is the mid one greater than k or smaller than k