Hackerss.com

hackerss
hackerss

Posted on

How to implement binary search in Java

How to implement binary search - Java:


/**
* This class implements binary search.
* @author Juan Antonio Rodríguez
* @version 1.0
*/
public class BinarySearch {
   /**
   * This method implements binary search.
   * @param array array to search.
   * @param key key to search.
   * @return int Obtains the index of the key in the array.
   */   
   public int binarySearch(int[] array, int key) {
       //Variable to store the index of the key in the array
       int index = -1;
       //Variable to store the start of the array
       int start = 0;
       //Variable to store the end of the array
       int end = array.length - 1;
       //Variable to store the middle of the array
       int middle = 0;
       //While the start is less than or equal to the end and the index is -1
       while (start <= end && index == -1) {
           //Calculate the middle of the array
           middle = (start + end) / 2;
           //If the key is equal to the value in the middle of the array, then set the index to middle
           if (key == array[middle]) {
               index = middle;
           } else {
               //If the key is less than the value in the middle of the array, then set the end to middle - 1
               if (key < array[middle]) {
                   end = middle - 1;
               } else {
                   //If the key is greater than the value in the middle of the array, then set the start to middle + 1
                   if (key > array[middle]) {
                       start = middle + 1;
                   }
               }
           }
       }
       //Return the index of the key in the array
       return index;
   }

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

      BinarySearch  binarySearch= new BinarySearch ();

      //Example 1: Search a key in an array with even number of elements

      //Array with even number of elements to search a key in it. The elements are sorted in ascending order. 
      int[] array = {1, 2, 3, 4, 5, 6, 7, 8};

      //Key to search in the array. The key is in the array. 
      int key = 5;

      //Search a key in an array with even number of elements. 
      int index = binarySearch.binarySearch(array, key);

      //Output: The index of the key in the array is 4. 

      System.out.println("The index of " + key + " in " + Arrays.toString(array) + " is " + index);

      //Example 2: Search a key in an array with odd number of elements

      //Array with odd number of elements to search a key in it. The elements are sorted in ascending order. 
      int[] array2 = {1, 2, 3, 4, 5, 6, 7};

      //Key to search in the array. The key is not in the array. 
      int key2 = 8;

      //Search a key in an array with odd number of elements. 
      int index2 = binarySearch.binarySearch(array2, key2);

      //Output: The index of the key in the array is -1. 

      System.out.println("The index of " + key2 + " in " + Arrays.toString(array2) + " is " + index2);

   }   
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)