Prune and search - Algoritmy.net

Prune and search - Algoritmy.net
Prune and search is a method for finding an optimal value by iteratively dividing a search space into two parts – the promising one, which contains the optimal value and is recursively searched and the second part without optimal value, which is pruned (thrown away). This paradigm is very similar to well know divide and conquer algorithms.

While the original approach has a  expected complexity, modified algorithm finds the n-th largest number in a expected complexity, where  is a small constant (approximately 4).

public static int pruneAndSearch(int[] array, int index, int left, int right) {

10.int boundary = left;

11.for (int i = left + 1; i < right; i++) {

12.if (array[i] > array[left]) { //place after the pivot every value, which is larger than the pivot

13.swap(array, i, ++boundary);

14.}

15.}

16.swap(array, left, boundary); //place pivot in the middle

17.//quicksort end

18. 

19.if (boundary == index) return array[boundary]; //found

20.else if (boundary > index) return pruneAndSearch(array, index, left, boundary); //prune the right branch

21.else return pruneAndSearch(array, index, boundary + 1, right); //prune the left branch 

22.}

23. 

24./**

25.* Swap elements in the given array

26.* @param array array

27.* @param left index of the element 1

28.* @param right index of the element 2

29.*/

30.private static void swap(int[] array, int left, int right) {

31.int tmp = array[right];

32.array[right] = array[left];

33.array[left] = tmp;

34.}

Read full article from Prune and search - Algoritmy.net