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 lb, int ub, int key )
{
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 algorithm, the array must first be in sorted order.
In closing, each search method has its own technique for sorting. While the end result is the same, the path to that point isn't. Understand the general idea of how each sort works and don't bother memorizing the Java algorithm. Lastly, the bubble sort is fine for small arrays, but gets bogged down with too many comparisons and switches when we encounter a large collection of data. The selection and insertion are much faster in this case. Use either with approximately equal results in efficiency.
|