算法竞赛宝典 分治算法 第k个数(不一样的二分)_第k大数分治算法

题目： 

N个无序的数（可能数目非常大），选出其中最大的K个数。

方法一：对所有元素进行排序，之后取出前K个元素，不提倡使用

思路：使用最快排序算法，选择快排 或 堆排

时间复杂度：O(n*logn) + O(K) = O(n*logn)

特点：需要对全部元素进行排序，K = 1 时，时间复杂度也为O(n*logn)

方法二：只需要对前K个元素排序，不需要对N-K个元素进行排序，不提倡使用

思路：使用 选择排序 或 起泡排序，进行K次选择，可得到第k大的数

时间复杂度：O(n*k)

//这个二分跟以前的二分不一样在于mid，这个的意思是以第一个为标准进行划分，最后确定于k的关系

#include<iostream>
#include<bits/stdc++.h>
const int N=100000+10;
using namespace std;
 
int a[N];
int b[N];
void binary_search(int left,int right)
{
	int i=left;
	int j=right;
	while(i!=j)
	{
		if(i<j)
		{
			if(a[i]>a[j])
			{
				swap(a[i],a[j]);
				swap(i,j);
			}
			else
				j--;
		}
		else
		{
			if(a[i]<a[j])
			{
				swap(a[i],a[j]);
				swap(i,j);
			}
			else
				j++;
		}
	}
	if(i>k)
	{
		binary_search(left,i-1);
	}
	else if(i<k)
	{
		binary_search(i+1,right);
	}
	else
	{
		for(int p=1; p<=n; p++)
		{
			if(b[p]==a[k])
			{
				printf("%d\n",p);
				break;
			}
		}
	}
}
int main()
{
	int n,k;
	while(cin>>n>>k)
	{
		for(int i=1; i<=n; i++)
		{
			scanf("%d",&a[i]);
			b[i]=a[i];
		}
		binary_search(1,n);
	}
	return 0;
}