Lesson 5.2 - Search Methods
Purpose: To learn how to search for numbers and text stored in arrays
I still haven't found what I'm looking for... We will now search an array to find the location of a unique, given value. As with sorts, there are many algorithms used to perfom searches. Let's learn two: LINEAR, and BINARY.
For each of the following, we assume that list is defined as follows:
int[] array = new int[n]; // n = some integer
THE LINEAR SEARCH ALGORITHM - aka SEQUENTIAL SEARCH
// Search "array" for the specified "key" value
public static int linearSearch( int array[], int key )
{
for ( int n = 0; n < array.length; n++ )
if ( array[ n ] == key ) // key found
return n;
return -1; // key not found
}
THE BINARY SEARCH ALGORITHM
// Search "array" for the specified "key" value
// lb = lower bound, ub = upper bound
public static int binSearch( int[] array, int key )
{
int lb=0, int ub=array.length-1;
while(lb <= ub)
{
int mid = (lb + ub) / 2; // compute midpoint
if ( key < array[mid])
{
ub = mid - 1; // repeat search in lower half;
}
else if ( key > array[mid])
{
lb = mid + 1; // repeat search in upper half;
}
else
{
return mid; // key found, return position
}
}
return -1; // key not found
}
Note that to use the binary search algorithm, the array must first be in sorted order.
BINARY SEARCH - Worst-Case determination
The strength of a binary search is that it reduces the number of "comparisons" needed to find the "key" value, thus speeding up the process of performing the search. Because the array is repeatedly being cut in half as we use the binary algorithm, the number 2 has a part in explaining how this method works. Below is a table for the worst-case number of comparisons for arrays sized from 1 to 10 elements:
Size |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
Worst-Case |
1 |
2 |
2 |
3 |
3 |
3 |
3 |
4 |
4 |
4 |
In closing, each search method has its own technique for searching. While the end result is the same, the path to that point isn't. Understand the general idea of how each search works and don't bother memorizing the Java algorithm. Lastly. the binary search is far more efficient when searching in very large arrays.
|