Linear versus Binary Search
Linear search is the name for the algorithm which looks at each item in order, until it finds what it is looking for (the target) or else runs out of items in the array. For an unsorted array, this is the best we can do.
Binary search is a much better algorithm, which however can only be used to search a SORTED array. It begins by breaking the sorted array into two half arrays. By comparing the target to the item at the midpoint, we can determine whether our target is in the first half or the second half, and thus we can throw away half the array. Now repeat the process on the half you retained. And so on.
It can be shown that linear search is of order O(n) while binary search is of order O(log n), where n is the size of the array. This means, for instance, that binary search of a sorted array of about 1,000 items will take roughly 10 steps (log 1000 = 10), so for arrays of that approximate length, binary search is 100 times faster than linear search. For arrays of about a million elements, binary search turns out to be roughly 50 thousand times faster than linear search!
Note: The branch of computer science that classifies, compares, and analyzes algorithms is called the theory of algorithms and complexity. We are touching slightly on that important topic here today.
Binary search algorithm is the foundation of all database programs.
Here we show a class that implements linear search and also binary search for arrays of char, int, and String. Note the polymorphism, using method overloading. Note also that all methods are static, so the methods are invoked using the class name instead of an object name. We also include a main method in the class for testing.
You should pay attention to the difference between the implementation of the search methods for arrays of primitive types versus arrays of Strings. Make sure you understand why they have to be different!
public class Search
{
//--------------------------------------------------------------
// Linear search method: searches an array of characters.
// Returns the index of the first element that matches search
// target, if possible. If no match is found, returns -1.
//--------------------------------------------------------------
public static int linear(char[] x, char target)
{
int index;
for (index=0; index < x.length; index++)
if (target == x[index]) return index;
return -1; //not found
}
//--------------------------------------------------------------
// Linear search method: searches an array of integers.
// Returns the index of the first element that matches search
// target, if possible. If no match is found, returns -1.
//--------------------------------------------------------------
public static int linear(int[] x, int target)
{
int index;
for (index=0; index < x.length; index++)
if (target == x[index]) return index;
return -1; //not found
}
//--------------------------------------------------------------
// Linear search method: searches an array of Strings.
// Returns the index of the first element that matches search
// target, if possible. If no match is found, returns -1.
//--------------------------------------------------------------
public static int linear(String[] x, String target)
{
int index;
for (index=0; index < x.length; index++)
if ( target.equals(x[index]) ) return index;
return -1; //not found
}
//--------------------------------------------------------------
// Binary search method: searches a SORTED array of characters.
// Returns the index of the first element that matches search
// target, if possible. If no match is found, returns -1.
//--------------------------------------------------------------
public static int binary(char[] x, char target)
{
int midpoint;
int start=0, end=x.length-1;
while (start <= end)
{
midpoint = (start + end)/2;
if (target < x[midpoint]) end = midpoint-1;
if (target == x[midpoint]) return midpoint;
if (target > x[midpoint]) start = midpoint+1;
}
return -1;
}
//--------------------------------------------------------------
// Binary search method: searches a SORTED array of integers.
// Returns the index of the first element that matches search
// target, if possible. If no match is found, returns -1.
//--------------------------------------------------------------
public static int binary(int[] x, int target)
{
int midpoint;
int start=0, end=x.length-1;
while (start <= end)
{
midpoint = (start + end)/2;
if (target < x[midpoint]) end = midpoint-1;
if (target == x[midpoint]) return midpoint;
if (target > x[midpoint]) start = midpoint+1;
}
return -1;
}
//--------------------------------------------------------------
// Binary search method: searches a SORTED array of Strings.
// Returns the index of the first element that matches search
// target, if possible. If no match is found, returns -1.
//--------------------------------------------------------------
public static int binary(String[] x, String target)
{
int midpoint;
int start=0, end=x.length-1;
while (start <= end)
{
midpoint = (start + end)/2;
if ( target.compareTo(x[midpoint]) < 0 ) end = midpoint-1;
if ( target.compareTo(x[midpoint]) == 0 ) return midpoint;
if ( target.compareTo(x[midpoint]) > 0 ) start = midpoint+1;
}
return -1;
}
//--------------------------------------------------------------
// A simple main method to test our Search methods.
//--------------------------------------------------------------
public static void main(String[] args)
{
char[] c = {'w', 'e', '9', 'q', '[', 'a', 'u', '3', 'z',
'b', '%', 'q', 'n', 'A', '-', 'D', 'k', 'I',
'S', 'q', 'T', '#', 'G', 'Y', 'E', '8'};
char[] d = {'A', 'C', 'E', 'I', 'O', 'P', 'U', 'X' , 'Z'};
int[] e = {10, 24, 32, 33, 40, 51, 53, 55, 61, 72};
String[] f = {"cat", "dog", "horse", "iguana", "llama", "monkey"};
System.out.println("Test linear (char):");
System.out.println(Search.linear(c,'#'));
System.out.println(Search.linear(c,'&'));
System.out.println("\nTest linear (int):");
System.out.println(Search.linear(e,61));
System.out.println(Search.linear(e,50));
System.out.println("\nTest linear (String):");
System.out.println(Search.linear(f, "cat"));
System.out.println(Search.linear(f, "elephant"));
System.out.println("\n\n\nNow we test binary (char):");
System.out.println(Search.binary(d,'E'));
System.out.println(Search.binary(d,'P'));
System.out.println(Search.binary(d,'Z'));
System.out.println(Search.binary(d,'A'));
System.out.println(Search.binary(d,'&'));
System.out.println("\nTest binary (int):");
System.out.println(Search.binary(e,32));
System.out.println(Search.binary(e,33));
System.out.println(Search.binary(e,10));
System.out.println(Search.binary(e,72));
System.out.println(Search.binary(e,50));
System.out.println("\nTest binary (String):");
System.out.println(Search.binary(f,"dog"));
System.out.println(Search.binary(f,"llama"));
System.out.println(Search.binary(f,"monkey"));
System.out.println(Search.binary(f,"cat"));
System.out.println(Search.binary(f,"elephant"));
}
}
Here is the output of our test:
[doty@weyl doty]$ javac Search.java [doty@weyl doty]$ java Search Test linear (char): 21 -1 Test linear (int): 8 -1 Test linear (String): 0 -1 Now we test binary (char): 2 5 8 0 -1 Test binary (int): 2 3 0 9 -1 Test binary (String): 1 4 5 0 -1
0 comments:
Post a Comment