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.

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 = { 6, 5, 1, 8, 3, 9, 4, 0, 2, 7 };     //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;   } }

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