 |
|
|
|
10/13/09 - Linear Search and Binary Search of an Array
|
|
|
|
 | A linear search of an array begins at the start of an array and continues from one element to the next until either the target value is found or the end of the array is reached. If the target value is found, the method returns the index of the target value. If the target value is not found, the method returns -1.
|
|
|
|
|
| A binary search of an array requires a sorted array to begin with. Assuming the array is sorted in ascending order, it sets a lower index value to 0 and an upper index to length-1, the index of the last element in the array. It then sets a middle index value to (lower + upper)/2 and compares the value at that index to the target value. If the target value matches the array value at the middle index, the middle index value is returned. If the target value is larger, then the lower index is set to middle+1 and the search continues. If the target value is smaller, then the upper index is set to middle-1 and the search continues. If the lower index is greater than the upper index, the value is not contained in the array, and the method returns -1.
|
|
|
|
|
| Create a class with a method that accepts a charge account number as its argument. The method should determine whether the number is valid by comparing it to the following list of valid charge account numbers stored in a file.
5658845 4520125 7895122 8777541 8451277 1302850
8080152 4562555 5552012 5050552 7825877 1250255
1005231 6545231 3852085 7576651 7881200 4581002
These numbers should be read into an array. First, use a linear search to locate the number passed as an argument. If the number is in the array, the method should return its index, indicating the number is valid. If the number is not in the array, the method should return -1, indicating the number is invalid. Just before returning the index or -1, your method should set a static variable indicating the number of comparisons made.
Second, sort the array and then use a binary search to locate the number passed as an argument. If the number is in the array, the method should return its index, indicating the number is valid. If the number is not in the array, the method should return -1, indicating the number is invalid. Just before returning the index or -1, your method should set a static variable indicating the number of comparisons made.
Write a program that tests your two methods by asking the user to enter a charge account number. The program should display a message indicating whether the number is valid or invalid and how many comparisons were made. Show results for every value in the file using both search methods. See the table below:
|
|
|
|
|
 |
|
;){kind=small}
;){kind=small}
