Chapter 8 Search and Sort - University of Arizona

Chapter 8 Search and Sort

?Rick Mercer

Binary Search

? Binary search serves the same service as sequential search, but faster

? Especially when there are many array elements

? You employ a similar algorithm when you look up a name in a phonebook

while the element is not found and it still may be in the array { if the element in the middle of the array is the matches store the reference and signal that the element was found else eliminate correct half of the array from further search

}

Binary Search

? We'll see that binary search can be a more efficient algorithm for searching.

? It works only on sorted arrays like this

? Compare the element in the middle ? if that's the target, quit and report success ? if the key is smaller, search the array to the left ? otherwise search the array to the right

? This process repeats until we find the target or there is nothing left to search

Some preconditions

For Binary Search to work

? The array must be sorted ? The indexes referencing the first and last elements

must represent the entire range of meaningful elements in the array

Binary search a small array

w Here is the array that will be searched

int n = 9; String[] a = new String[n]; // Insert elements in natural order (according to // the compareTo method of the String class a[0] = "Bob"; a[1] = "Carl"; a[2] = "Debbie"; a[3] = "Evan"; a[4] = "Froggie"; a[5] = "Gene"; a[6] = "Harry"; a[7] = "Igor"; a[8] = "Jose"; // The array is filled to capacity in this example

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download