一道腾讯面试题

public static int selectMiddle(int[] data) {
		int mid = data.length / 2 + 1;
		return selectMiddle(data, 0, data.length - 1, mid);
	}
	
	private static int selectMiddle(int[] data, int first, int last, int i) {
		if(first == last)
			return data[first];
		int index = partition(data, first, last);
		int k = index - first + 1;
		if(i == k)
			return data[index];
		else if(i < k)
			return selectMiddle(data, first, index - 1, i);
		else
			return selectMiddle(data, index + 1, last, i - k);
	}
private static int partition(int[] data, int first, int last) {
		int index = (first + last) >> 1;
		int pivot = data[index];
		swap(data, index, last);
		
		int i = first;
		int j = last - 1;
		while(true) {
			while(i < j && data[i] <= pivot)
				i++;
			while(j >= i && data[j] >= pivot)
				j--;
			if(j < i)
				break;
			swap(data, i++, j--);
		}
		swap(data, i, last);
		return i;
	}