Binary Search (with Recursion) in java

This algorithm help us in finding element by using Binary Search(Recursion).

We may also use simple way of searching i.e. Linear Search which is slower than Binary Search.

We’ll be using the BinarySearchArray class to encapsulate the array and its algorithms.
The most important method of this class is the binarySearchRecursive() method, which uses a binary search to locate a specified data item.
The binarySearchRecursive() method searches for a specified item by repeatedly dividing in half the range of array elements to be considered.



The method looks like this:

   /**
   * Find element using Binary search recursively
   */
public Integer binarySearchRecursive(int key,int lowerBound, int upperBound) {
                 int mid;   //points to mid of array.
                 mid = (lowerBound + upperBound) / 2;
                 if (ar[mid] == key) {
                       System.out.print("\nElement=" + key + " found at position="
                                     + mid);
                       return mid;
                 }else if (lowerBound > upperBound) {
                       System.out.print("\nElement=" + key + " not found");
                       return index;
                 }
                 else if (ar[mid] > key) {
                       upperBound = mid - 1; // Element is in lower half
                       return binarySearchRecursive(key,lowerBound,upperBound);
                 } else {
                       lowerBound = mid + 1; // Element is in upper half
                       return binarySearchRecursive(key,lowerBound,upperBound);
                 }
   }

                       ArrayList custom implementation.

  
Logic explanation >

The method begins by setting lowerBound and upperBound variables to the first and
last occupied cells in the array.
We also define mid variable variable mid which points to middle position of array.
Setting these variables specifies the range where the item we’re looking for, key, can be found.

If mid points to the desired item, so we first check if this is true. If it is, we’ve found the item, so we return with mid(as it is position at which we have found element).
Each time through the loop we divide the range in half. Ultimately, the range will get so small that it can’t be divided any more. We check this in the next statement-
If lowerBound is greater than upperBound (Element has not been found and we return).

If mid is not pointing at the desired item, and the range is still big enough, we’ll divide the range in half. We compare the value at the current index, a[mid], which is in the middle of the range, with the value to be found i.e. key.

Now there can be 2cases>
Case1>
If key is larger, we know we should look in the upper half of the range.
Accordingly, we move lowerBound up to mid. Actually, we move it one cell beyond
mid because we’ve already checked mid itself at the beginning of the loop.
Case2>
If key is smaller than a[mid], we know we should look in the lower half of
the range. So we move upperBound down to one cell below mid.





Full Program/SourceCode >
/**
*This class holds reference of array, in which data has to be searched.
*/
class BinarySearchArray {
   private int ar[];
   private int index; // holds current position of array, by default it is
                                     // initialized with 0
  
   /**
   * Constructor for initializing array
   */
   public BinarySearchArray(int maxSize) {
          ar = new int[maxSize];
          index = 0;
   }
   /**
   * Insert values into array (Array must remain sorted, because binary search
   * works on sorted array)          
   */
   public void insert(int value) {
          int j;
          for (j = 0; j < index; j++)
                 // find position at which value should go
                 if (ar[j] > value) // linear search
                       break;
          for (int x = index; x > j; x--)
                 // move bigger elements up
                 ar[x] = ar[x - 1];
          ar[j] = value; // insert it
          index++; // increment size
   }
  
   /**
   * Wrapper method which calls recursive binary search method.
   */
   public Integer binarySearch(int key) {
          int lowerBound = 0;  //points to first occupied cell in array.
          int upperBound = index - 1; //points to last occupied cell in array.
          return binarySearchRecursive(key,lowerBound,upperBound);
   }
   /**
   * Find element using Binary search recursively
   */
   public Integer binarySearchRecursive(int key,int lowerBound, int upperBound) {
                 int mid;   //points to mid of array.
                 mid = (lowerBound + upperBound) / 2;
                 if (ar[mid] == key) {
                       System.out.print("\nElement=" + key + " found at position="
                                     + mid);
                       return mid;
                 }else if (lowerBound > upperBound) {
                       System.out.print("\nElement=" + key + " not found");
                       return index;
                 }
                 else if (ar[mid] > key) {
                       upperBound = mid - 1; // Element is in lower half
                       return binarySearchRecursive(key,lowerBound,upperBound);
                 } else {
                       lowerBound = mid + 1; // Element is in upper half
                       return binarySearchRecursive(key,lowerBound,upperBound);
                 }
   }
   /**
   * Display Array
   */
   public void display() {
          System.out.print("Displaying Array: ");
          for (int i = 0; i < index; i++) {
                 System.out.print(ar[i] + " ");
          }
   }
}
 
 
 
/** Copyright (c), AnkitMittal www.JavaMadeSoEasy.com */
/**
* Main class
*/
public class BinarySearchRecusiveApp {
   public static void main(String[] args) {
          int maxSize = 10; // Initial size of array
          BinarySearchArray bSearchArray = new BinarySearchArray(maxSize);
          bSearchArray.insert(11);
          bSearchArray.insert(22);
          bSearchArray.insert(33);
          bSearchArray.insert(99);
          bSearchArray.insert(55);
          bSearchArray.insert(77);
          bSearchArray.insert(66);
          bSearchArray.insert(88);
          bSearchArray.insert(44);
          bSearchArray.insert(1);
          bSearchArray.display();
          bSearchArray.binarySearch(88); // FOUND
          bSearchArray.binarySearch(-1); // NOT FOUND
          bSearchArray.binarySearch(73); // NOT FOUND
   }
}
/** OUTPUT
Displaying Array: 1 11 22 33 44 55 66 77 88 99
Element=88 found at position=8
Element=-1 not found
Element=73 not found
*/


Complexity of Binary Search >

Best,average and worst case >

Best Case :   O(1) ; when key is middle element.
Average Case : O(logN)
Worst Case :     O(logN)

>No. of comparisons : O(logN) in average/worst case  
& 1 in best case(when key is middle element).

Explanation >
Complexity of Binary Search is O(logN), where N is number of elements.

It doesn't half search time, that wouldn't make it log(n). It decreases it logarithmically.
If you had 128 entries in a table and had to search linearly for your value, it would probably take around 128 entries on average to find your value. That's log(n) or linear time.
With a binary search, you eliminate 1/2 the possible entries each iteration, such that at most it would only take 7 compares to find your value (log base 2 of 128 is 7 or 2 to the 7 power is 128.) This is the power of binary search.


Comparisons needed in Binary Search >

Searching 10 item in Binary search will take average of 4 searches.
Searching 100 item in Binary search will take average of 7 searches.
Searching 1000 item in Binary search will take average of 10 searches & so on….

Number of elements
Comparisons Needed
10
4
100
7
1000
10
10,000
14
100,000
17
1,000,000
20
10,000,000
24
100,000,000
27
1,000,000,000
30


Complexity of Binary Search in graph >




RELATED LINKS>

Sorting

Advanced Sorting

Searching



No comments:

Post a Comment