Do you remember playing the game "Guess a Number", where the responses to the statement "I am thinking of a number between 1 and 100" are "Too High", "Too Low", or "You Got It!"? A strategy that is often used when playing this game is to divide the intervals between the guess and the ends of the range in half. This strategy helps you to quickly narrow in on the desired number.

When searching an array, the binary search process utilizes this same concept of splitting intervals in half as a means of finding the "key" value as quickly as possible.

If the array that contains your data is in order (ascending or descending), you can search for the key item much more quickly by using a binary search algorithm ("divide and conquer").

Consider the following array of integers:

Array of Integers in Ascending order 13 24 34 46 52 63 77 89 91 100
0 1 2 3 4 5 6 7 8 9

We will be searching for the integer 77:

First, the middle is located by adding the array subscript of the first character to the subscript of the last character and dividing by two: (0 + 9) / 2 = 4 The actual middle would be between the elements 4 and 5. Integer division is used to arrive at element 4 as the middle.

Element 4 holds the integer 52, which comes before 77. We know that 77 exists in that portion of the array to the right of 52. We need to find the middle of the right portion of the array by using the formula (5 + 9) / 2 = 7

Element 7 holds the integer 89, which comes after 77, so we next find the middle of the portion of the array to the right of 52, but to the left of 89 using (5 + 6) / 2 = 5

Element 5 holds the integer 63, which comes before 77, so we subdivide again
(6 + 6) / 2 = 6 and element 6 holds the integer 77.

Binary search method:
binary_search (array, 0, 10, key);

=================
The arguments/parameters are:
array - the name of a sorted array
lowerbound - index of first element to
search, array [0]
upperbound - (range to be searched)
index of last element is array[10 - 1].
key: item we wish to find.

import java.io.*;

import BreezyGUI.*;
public class VitalStatistics

{

     public static void main(String[] args)

    {

        int key = 77;

        int[ ] array = new int [10];

        for (int i = 0; i < 10; i++)

             array[ i ]=Console.readInt("Enter integer:  ");

        binary_search (array, 0, 10, key);

    }

 
//Binary Search Method

  // Method accepts a pre-sorted array, the index of the starting element for the search,

  // the range (number) of elements to be searched,

  // and the number for which we are searching.

   public static void binary_search(int[ ] array, int lowerbound, int upperbound, int key)

   {

       int position;

       int compare_count = 1;
     // calculate initial search position.

     position = ( lowerbound + upperbound) / 2;
     while((array[position] != key) && (lowerbound < upperbound))

     {

         compare_count++;

         if (array[position] > key) // if the value in the search position is greater than the number for ..

         {                                                  // which we are searching, change upperbound to

              upperbound = position - 1;   // search position minus one.

         }

              else

        {

              lowerbound = position + 1; // Else, change lowerbound to search position plus one.

        }

       position = (lowerbound + upperbound) / 2;

     }

     if (lowerbound < upperbound)

     {

           System.out.println("A binary search found the number in " + compare_count + "comparisons.");

           System.out.println("The number was found in array subscript" + position);

     }

     else

          System.out.println("Number not found by binary search after " +compare_count

                                                           + "comparisons.");

  }
}



This method prints the result of the search.  It is also possible to return the result of the search.  Return the position if the value is found and return a negative number if the result is not found.