Palantir 电面面经

同没有听懂followup...求楼主提示...谢谢呀！

老印没说错....  
quick select: average O(n), worst case O(n^2)
median of medians selection: worst case O(n);

这还真不是烙印黑你

这是一道送分题啊  

求教binary search怎么做？

第二题，根据给的范围的最小值和最大值对k值修改。
例子[1, 3, 2, 5, 7, 3, 4], range [0, 3]，k＝3
有0个数比范围［0，3］的最小值0小，所以k＝3
如果范围为［2，5］，原数组有一个1比2小，所以k＝4，在原数组中找第4大的值