二分找第K大数

题目描述:

数组a ( a[1]~a[n]，n≥1 ) 中的数据，为无序的整数，为了在数组a中查找第k大(1≤k≤n)的整数，小李借鉴对分查找的思想，编写的 python 程序段如下：

输入格式:

第一行，一个数n。

第二行，n个数，以一个逗号分隔每个数。

第三行，一个数中k。

输出格式:

一个表示第K大的数。

数据范围:

n<=100,000

a数组中的每个数小于10000

样例输入:

9
12,4,67,23,90,6,7,11,12
4

样例输出:

12

提示:

请完善下面的程序（改成题目样例输入要求的输入）：

a = [12,4,67,23,90,6,7,11,12]
n = len(a)
k = int( input() )
low=a[0] ; high=a[0]
for i in range( 1,n):
    if a[i] < low : low = a[i]
    if a[i] > high: high = a[i]
while low < high:
    m=(low+high) // 2
    cnt = 0
    for i in range( n ):
        if a[i] > m : cnt += 1
    if cnt >= k:
       __________(1)___________    #填空1
    else :
        __________(2)___________  #填空2
print(  high )

时间限制: 1000ms
空间限制: 256MB

---

来源: 原创