寻找第K大O(n)解法（快排+二分）

最近面试东京株式会社遇到这个题，特地来刷一下。
思路：
快排+二分，与快排不同的是，利用二分法每次都减少了一半的不必要排序。
当high=low小于k的时候，在后半部分搜索，
当high=low大于k的时候，在前半部分搜索。

代码：

# -*- coding:utf-8 -*-
import sys
def findKth(a, start, end, K):
    low, high = start, end
    key = a[start]
    while start < end:
        while start < end and a[end] <= key:
            end-=1
        a[start] = a[end]
        while start < end and a[start] >= key:
            start+=1
        a[end] = a[start]
    a[start] = key
    if start < K-1:
        return findKth(a, start+1, high, K)
    elif start > K-1:
        return findKth(a, low, start-1, K)
    else:
        return a[start]

try:
    while(1):
        line=sys.stdin.readline()
        if line=='': break
        lines = line.strip().replace('[','').replace(']','').split(',')
        lines = list(map(int,lines))
        n, K = lines[-2], lines[-1]
        val = findKth(lines, 0, n-1, K)
        print(val)
except:
    pass

麻豆出品，必出精品！