Code for Finding Median in Linear Time

import java.util.ArrayList;
 
public class LinearMedian {
	public int mMedian(int[] raw) {
		if (raw.length == 1) return raw[0];
		int[] medianArray = new int[(raw.length - 1) / 5 + 1];
		for (int i = 0; i < (raw.length - 1) / 5 + 1; i++) {
			int start = i * 5;
			int end = i * 5 + 5;
			int[] temp;
			if (end <= raw.length)
				temp = new int[5];
			else {
				temp = new int[raw.length - start];
			}
			for (int j = start; j < end && j < raw.length; j++) {
				temp[j - start] = raw[j];
			}
			medianArray[i] = smallMedian(temp);
		}
		return findMedian(medianArray, medianArray.length / 2);
	}
 
	public int smallMedian(int[] raw) {
		for (int i = 0; i < raw.length - 1; i++) {
			for (int j = i + 1; j < raw.length; j++) {
				if (raw[i] < raw[j]) {
					int temp = raw[i];
					raw[i] = raw[j];
					raw[j] = temp;
				}
			}
		}
		return raw[raw.length / 2];
	}
 
	public int findMedian(int[] raw, int k) {
		if (raw.length == 1) return raw[0];
		int median = mMedian(raw);
		if (raw.length <= 5) return median;
		return partitionMedian(raw, median, k);
	}
 
	public int partitionMedian(int[] raw, int median, int k) {
		if (raw.length == 1) return raw[0];
		ArrayList<Integer> left = new ArrayList<Integer>();
		ArrayList<Integer> right = new ArrayList<Integer>();
		for (int i = 0; i < raw.length; i++) {
			if (raw[i] < median) left.add(raw[i]);
			else if (raw[i] > median) right.add(raw[i]);
		}
		if (k > left.size() && k < raw.length - right.size())
			return median;
		else if (k < left.size()) {
			int[] leftArray = new int[left.size()];
			for (int i = 0; i < left.size(); i++) {
				leftArray[i] = left.get(i);
			}
			return findMedian(leftArray, k);
		}
		else {
			int[] rightArray = new int[right.size()];
			for (int i = 0; i < right.size(); i++) {
				rightArray[i] = right.get(i);
			}
			return findMedian(rightArray, k - raw.length + right.size());
		}
	}
 
	public static void main(String[] args) {
		int[] input = new int[] {6, 2, 1, 5, 3, 7, 9, 10, 123, 4, 3};
		LinearMedian test = new LinearMedian();
		System.out.println(test.findMedian(input, input.length / 2));
	}
}

Leave a Reply

Your email address will not be published. Required fields are marked *