Recursive Binary Search in java

Posted By: Java Examples - 3:16 PM

Share

& Comment

Algorithm :
  •  Algorithm is quite simple. It can be done either recursively or iteratively: 
  •  get the middle element; 
  • if the middle element equals to the searched value, the algorithm stops; otherwise, two cases are possible: 
    • searched value is less, than the middle element. 
    • In this case, go to the step 1 for the part of the array, before middle element. searched value is greater, than the middle element. In this case, go to the step 1 for the part of the array, after middle element.

Java version of the Recursive binary search is given below :

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package binarysearcharray;

/**
 *
 * @author ACHCHUTHAN
 */
public class BinarySearchRec {

    int[] array = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30};

    public int binarySearch(int key, int l, int r) {
        if (r < l) {
            return -1;
        }
        int mid = (l + r) / 2;
        if (key == array[mid]) {
            return mid;
        }
        if (key < array[mid]) {
            return binarySearch(key, l, mid - 1);
        } else {
            return binarySearch(key, mid + 1, r);
        }

    }

    public static void main(String[] args) {
        BinarySearchRec b = new BinarySearchRec();

        for (int i = 2; i < 32; i += 2) {

            System.out.println("Search for element " + i);
            System.out.println("This element is found at " + b.binarySearch(i, 0, 14));
            System.out.println("=======+============+=======+==============");
        }
    }
}

Output of this program :
run:

Search for element 2
This element is found at 0
=======+============+=======+==============
Search for element 4
This element is found at 1
=======+============+=======+==============
Search for element 6
This element is found at 2
=======+============+=======+==============
Search for element 8
This element is found at 3
=======+============+=======+==============
Search for element 10
This element is found at 4
=======+============+=======+==============
Search for element 12
This element is found at 5
=======+============+=======+==============
Search for element 14
This element is found at 6
=======+============+=======+==============
Search for element 16
This element is found at 7
=======+============+=======+==============
Search for element 18
This element is found at 8
=======+============+=======+==============
Search for element 20
This element is found at 9
=======+============+=======+==============
Search for element 22
This element is found at 10
=======+============+=======+==============
Search for element 24
This element is found at 11
=======+============+=======+==============
Search for element 26
This element is found at 12
=======+============+=======+==============
Search for element 28
This element is found at 13
=======+============+=======+==============
Search for element 30
This element is found at 14
=======+============+=======+==============
BUILD SUCCESSFUL (total time: 0 seconds)

About Java Examples

I’m passionate about Web Development and Programming and I go to extreme efforts to meet my passion. I’m a believer of learning the fundamentals first. I try to understand everything little bit more than the average.

Copyright © 2016 Java Examples ACHCHUTHAN.ORG. Designed by Templateism .