|
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.
Remember:
You must start with a pre-sorted array!!!
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:
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. |
|
//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.
|
