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.
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.
|