tl  tr
  Home | Tutorials | Articles | Videos | Products | Tools | Search
Interviews | Open Source | Tag Cloud | Follow Us | Bookmark | Contact   
 Data Structures > Search > Binary Search Recursive

Binary Search Recursive 

Binary search is faster when compared to Linear search. The pre condition for Binary Search to work is the elements of array should be sorted. Its time complexity is O(log n). It works as follows,

  1. Get the middle element of list.
  2. If search element is less than middle element then perform Step1 by passing first sub half (first element to middle element) as a list.
  3. If search element is greater than middle element then perform Step1 by passing second sub half (middle element to last element) as a list.
  4. If search element matches with middle element then search is finished.
This example shows binary search implementation using recursive algorithm.

File Name  :  
com/bethecoder/tutorials/ds/search/BinarySearchRecursive.java 
Author  :  Sudhakar KV
Email  :  [email protected]
   
package com.bethecoder.tutorials.ds.search;

import java.util.Arrays;

public class BinarySearchRecursive {

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

    int[] list = 651839402};

    //Make sure to sort the list if its not sorted already
    Arrays.sort(list);
    System.out.println("Sorted array : " + Arrays.toString(list));

    //Binary Search
    binarySearch(list, 2);
    binarySearch(list, 8);
    binarySearch(list, 12);
  }

  /**
   * The precondition for binary search is the search list is sorted.
   
   @param list
   @param searchEle
   @return
   */
  public static int binarySearch(int[] sortedList, int searchEle) {
    int index = binarySearch(sortedList, 0, sortedList.length - 1, searchEle);
    System.out.println(searchEle + " found in array at index : " + index);
    return index;
  }

  public static int binarySearch(int[] sortedList, int startIndex, int endIndex, int searchEle) {
    if (startIndex > endIndex) {
      return -1;
    }

    int midIndex = startIndex + (endIndex - startIndex)/2;

    if (searchEle < sortedList[midIndex]) {
      return binarySearch(sortedList, startIndex, midIndex-1, searchEle);
    else if (searchEle > sortedList[midIndex]) {
      return binarySearch(sortedList, midIndex+1, endIndex, searchEle);
    }

    //means searchEle == sortedList[midIndex]
    return midIndex;
  }

}
   

It gives the following output,
Sorted array : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
2 found in array at index : 2
8 found in array at index : 8
12 found in array at index : -1



 
  


  
bl  br