POJ-2388-Who's in the Middle-easy.txt

/**
POJ-2388-Who's in the Middle
2015-10-24 23:15:38
xuchen
**/
#include "stdio.h"
#include <cmath>
#include <algorithm>
#include <queue>
#include <stdlib.h>
#include <cstring>
using namespace std;

const int N = 10005;
int a[N];

int find(int l, int r, int k)
{
	if(l==r)
		return a[l];
	
	int pos = l+1;
	int x = a[l];
	int tmp;
	for(int i=l+1; i<=r; i++)
	{
		if(a[i]<=x)
		{
			tmp = a[pos];
			a[pos] = a[i];
			a[i] = tmp;
			pos++;
		}
	}
	pos--;
	a[l] = a[pos];
	a[pos] = x;
	if(pos-l+1 == k)
		return a[pos];
	if(pos-l+1 < k)
		return find(pos+1, r, k-(pos-l+1));
	else
		return find(l, pos-1, k);
}
int main()
{
	int n;
	scanf("%d", &n);
	for(int i=0; i<n; i++)
	{
		scanf("%d", &a[i]);
	}
	printf("%d\n", find(0, n-1, n/2+1));
	return 0;
}