Difference between revisions of "Searching Arrays"
(→Linear Search) |
|||
Line 10: | Line 10: | ||
1) Our search value has been found, or <br> | 1) Our search value has been found, or <br> | ||
2) We have reached the end of the array (in other words, we have not found the value.)<br><br> | 2) We have reached the end of the array (in other words, we have not found the value.)<br><br> | ||
+ | |||
+ | Example: find "McAdams" in the telephone book.<br> | ||
+ | Using a linear search, the algorithm would open the phone book to page 1. On page 1, we would check every name checking if it matches "McAdams". If "McAdams" is not on the first page, we would flip to the second page, and again, check every name for a match to "McAdams". We would continue this until eventually we have found the "McAdams" entry in the phone book, or there was no match. | ||
Here is the algorithm for completing a linear search: | Here is the algorithm for completing a linear search: | ||
Line 33: | Line 36: | ||
− | If our array is sorted | + | If our array is sorted in ascending order, our linear search algorithm can be a step more efficient. |
Example: | Example: | ||
− | Unsorted array | + | <pre> |
− | |10|50|60|40|20| | + | Unsorted array: Sorted array: |
− | + | |10|50|60|40|20| |10|20|40|50|60| | |
− | + | </pre> | |
− | |10|20|40|50|60| | + | |
+ | Using the sorted array above, if we were searching for the value "30", we would know after checking element 0 ("10"), element 1 ("20"), and then element 2 ("40"), that we will not find the value "30" since every element after element 2 will be greater than or equal to "40". | ||
− | + | Furthermore, our phone book example, we would know that once we have reached a name that would come after "McAdams" alphabetically, we can stop our search, "McAdams" is not in the phone book. | |
A simple addition to our for loop will do the trick: | A simple addition to our for loop will do the trick: |
Revision as of 11:47, 30 November 2007
COMP 1010 Home > Selection Search Algorithm
IntroductionNow that we have learned how to create an array, what can we do with it? One common application involves searching the array for a particular value.
There are a number of approaches to searching array, some more efficient than others. Two approaches are discussed here: 1. a linear search is the easiest search algorithm to implement, but is not very efficient; 2. a binary search can be implemented only on a sorted array, but it is far more efficient than a linear search.
|
---|
{{{Body}}}
Linear Search
A linear search can be used to locate a value in an array. A linear search checks each element one after another for a match to our search value until one of two things happens:
1) Our search value has been found, or
2) We have reached the end of the array (in other words, we have not found the value.)
Example: find "McAdams" in the telephone book.
Using a linear search, the algorithm would open the phone book to page 1. On page 1, we would check every name checking if it matches "McAdams". If "McAdams" is not on the first page, we would flip to the second page, and again, check every name for a match to "McAdams". We would continue this until eventually we have found the "McAdams" entry in the phone book, or there was no match.
Here is the algorithm for completing a linear search:
public static int linearSearch (int[] list, int searchValue) { int counter; //loop iterator int result; //store element where searchValue is found result = -1; //return -1 if searchValue is not found for (counter=0; result == -1 && counter<list.length; counter++) {//loop until searchValue is found or the array is out of bounds. if (list[counter] == searchValue) {//found searchValue! end loop. result = counter; } }//for return result; }//linearSearch()
If our array is sorted in ascending order, our linear search algorithm can be a step more efficient.
Example:
Unsorted array: Sorted array: |10|50|60|40|20| |10|20|40|50|60|
Using the sorted array above, if we were searching for the value "30", we would know after checking element 0 ("10"), element 1 ("20"), and then element 2 ("40"), that we will not find the value "30" since every element after element 2 will be greater than or equal to "40".
Furthermore, our phone book example, we would know that once we have reached a name that would come after "McAdams" alphabetically, we can stop our search, "McAdams" is not in the phone book.
A simple addition to our for loop will do the trick:
searchValue >=list[counter]
This completes our algorithm as follows:
public static int linearSearch (int[] list, int searchValue) { int counter; int result; result = -1; for (counter=0; result == -1 && counter<list.length && searchValue>=list[counter]; counter++) { if (list[counter] == searchValue) { result = counter; } }//for return result; }//linearSearch()
Selection Searching
Selection searches are often used in instances where the kth smallest item must be found. The easiest way to do this is to first sort the array into ascending (or descending) order, and then iterate through each item until the conditions have been satisfied.
The idea behind a selection sort is very simple: iterate through each element in the array, and for each element look at all remaining elements to see if there is something smaller that should be in this position. If there is, exchange the two values.
Example: sort this array
|30|10|20|40|60|
1) Outer loop: iterate through each element
i = 0 (30)
2) Inner loop: iterate through the remaining elements to find a smaller element that should be in this position
j = 1 (10)
3) Since the element at i is greater than the element at j, swap them - the array will now be:
|10|30|20|40|60|
4) Again with the inner loop, we will move to the next element and compare:
i = 0 (10), j = 2 (20)
Since all the other elements in the list are greater than the 0th (10), nothing else will happen for this outer loop.
Loop 2: In the outer loop, we will move to the next element (1) and loop through the remaining elements (starting at 2)
i = 1 (30), j = 2(20)
Since the element at i is greater than the element at j, swap them and continue, giving us this array (which is now sorted!)
|10|20|30|40|60|
Here is an example of a very simple selection sorting algorithm:
// Selection sort algorithm public static void selectionSort(int[] haystack) { for (int i = 0; i < haystack.length - 1; i++) { for (int j = i + 1; j < haystack.length; j++) { if (haystack[i] > haystack[j]) { //... Exchange elements int temp = haystack[i]; haystack[i] = haystack[j]; haystack[j] = temp; } } } }
After the list has been sorted, you can then iterate through the list simply using a for loop.
// selectionSearch - returns the index at which the value was found, or -1 if it was not found public static int selectionSearch(int needle, int[] haystack) { for (int i = 0; i < haystack.length; i++) { if (needle == haystack[i]) { return i; // if the value was found, return its index } } return -1; // if the value has not been found return -1 }
Binary Search
To help understand how the binary search works, consider this scenario:
You are using a phone book to look up a friend with the last name “McAdams”. If you used a sequential search method, you would open the phone book to the first page, then flip to the second page, continuing page by page until you have reached the M’s, and finally find McAdams.
Is that realistic? No! You would open the middle of the phone book, check if M's are on the right, or the left, and continue cutting the phone book until you find the right page.
This is the idea of the binary search. If we are searching for an element in a sorted array, we can inspect a single item and eliminate half of the array each inspection.
Here is an example of how the binary search works. Example: search for “40” in this array:
|10|20|30|40|50|
1) Inspect the middle element (30).
2) Is "40" this middle element, or to the left, or right of the middle element? It's on the right.
3) Eliminate the left portion of the array.
|30|40|50|
4) Inspect the new middle element (40).
5) Is "40" this middle element, or to the left, or right of the middle element? It's the middle element.
6) Binary search is done - we have found the "40" in element 3.
Now that you understand how the binary search works, let's look at the Binary Search Algorithm:
public static int binarySearch(int[] list, int searchValue) { int left; //left element index int right; //right element index int middle; //middle element index int result; // int middleElement; // result = -1; left = 0; right = list.length-1; while ((left <= right) && (result == -1)) { middle = (left + right) / 2; middleElement = list(middle); if (middleElement == searchValue) { result = middle; } else if (middleElement < searchValue) { left = middle + 1; } else if (middleElement > searchValue) { right = middle – 1; } }//while return result; }//binarySearch()