O(n) look for the median(or any target rank) in an array

 

 1 class Solution {
 2   public static void main(String[] args) {
 3     Solution solution = new Solution();
 4     solution.findMedian(new int[]{4, 1, 9});
 5     solution.findMedian(new int[]{4, 1, 9, 3});
 6     solution.findMedian(new int[]{4, 1, 9, 3, 0, 6, 1, 6, 4});
 7     solution.findMedian(new int[]{-1, 4, 1, 9, 3, 0, 6, 1, 6, 4});
 8     solution.findMedian(new int[]{4, 1, 9, 3, 0, 6, 1, 6, 4, 2, 3});
 9     solution.findMedian(new int[]{4, -10, -22, 1, 9, 3, 0, 6, 1, 6, 4, 2, 3});
10     solution.findMedian(new int[]{4, 1, 9, 3, 0, 6, 12, 13, 1, 6, 4, 10, 2, 3});
11   }
12 
13   void findMedian(int[] arr) {
14     if (arr.length % 2 == 1) {
15       int found = findSingleTarget(arr, 0, arr.length - 1, arr.length / 2);
16       System.out.println(String.format("Rank (%d) found using findSingleTarget algorithm: %d", arr.length / 2, found));
17     } else {
18       int found1 = findSingleTarget(arr, 0, arr.length - 1, (arr.length - 1) / 2);
19       // We don't need to look for twice, should be optimizable.
20       int found2 = findSingleTarget(arr, 0, arr.length - 1, arr.length / 2);
21       System.out
22           .println(String.format("Rank (%d, %d) found using findSingleTarget algorithm: %s", (arr.length - 1) / 2,
23               arr.length / 2, (found1 + found2) / 2.0));
24     }
25 
26     Arrays.sort(arr);
27     System.out.println(String
28         .format("Sorted array: %s Total count: %d, number in the middle(%d): %d", Arrays.toString(arr), arr.length,
29             arr.length / 2, arr[arr.length / 2]));
30     System.out.println();
31   }
32 
33   /**
34    * @param target is the rank(index) of a value, which we are looking for, if this arr is sorted
35    */
36   int findSingleTarget(int[] arr, int leftInclusive, int rightInclusive, int target) {
37     if (leftInclusive > rightInclusive) {
38       throw new IllegalArgumentException();
39     }
40     if (leftInclusive == rightInclusive) {
41       if (leftInclusive == target) {
42         return arr[leftInclusive];
43       }
44       throw new IllegalArgumentException();
45     }
46 
47     int left = leftInclusive;
48     int right = rightInclusive;
49 
50     int pivot = arr[left]; //use the first element as the pivot
51     ++left;
52 
53     while (left <= right) {
54       int current = arr[left];
55       if (current <= pivot) {
56         //lazy "swap" pivot with left
57         arr[left - 1] = arr[left];
58         ++left;
59       } else {
60         //swap left and right
61         swap(arr, left, right);
62         --right;
63       }
64     }
65     int pivotIndex = left - 1;
66     arr[left - 1] = pivot;
67     if (pivotIndex == target) {
68       return pivot;
69     }
70 
71     if (pivotIndex < target) {
72       return findSingleTarget(arr, pivotIndex + 1, rightInclusive, target);
73     }
74 
75     return findSingleTarget(arr, leftInclusive, pivotIndex - 1, target);
76   }
77 
78   private void swap(int[] array, int a, int b) {
79     int tmp = array[a];
80     array[a] = array[b];
81     array[b] = tmp;
82   }
83 }