Pacific-Design.com

    
Home Index

1. Algorithms

2. Binary Search

Algorithms / Binary Search /

Java Recursion - Recursive Binary Search

import java.util.Arrays;

public class RecursiveBinarySearch {

    /*----------------------------------------------------------------------------*/
    public static int recursion(int[] array, int key, int start, int end ) {

        if (start < end) {

            int mid = start + ((end - start) / 2);
            System.out.println("element = " + mid);

            if (key < array[mid]) {         // key is smaller than middle
                return recursion(array, key, start, mid);

            } else if (key > array[mid]) {  // key is bigger than middle
                return recursion(array, key, mid + 1, end);

            } else {                        // key is equal to middle
                return mid;
            }
        }

        return -(start + 1); // invalid range
    }

    /*----------------------------------------------------------------------------*/
    public static void main(String[] args) {

        int[] array = {4, 3, 2, 6, 9, 1, 5, 0, 7, 8};
        Arrays.sort(array);
        System.out.println("array = " + Arrays.toString(array));

        for(int i=0; i<array.length; i++) {
            int index = recursion(array, array[i], 0, array.length);
            System.out.println("Found "+ array[i] + " at " + index + " index\n");
        }

    }
    /*----------------------------------------------------------------------------*/

}

/*
Output

array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
element = 5
element = 2
element = 1
element = 0
Found 0 at 0 index

element = 5
element = 2
element = 1
Found 1 at 1 index

element = 5
element = 2
Found 2 at 2 index

element = 5
element = 2
element = 4
element = 3
Found 3 at 3 index

element = 5
element = 2
element = 4
Found 4 at 4 index

element = 5
Found 5 at 5 index

element = 5
element = 8
element = 7
element = 6
Found 6 at 6 index

element = 5
element = 8
element = 7
Found 7 at 7 index

element = 5
element = 8
Found 8 at 8 index

element = 5
element = 8
element = 9
Found 9 at 9 index
*/