Revision as of 11:56, 27 November 2007

COMP 1010 Home > Selection Search Algorithm

{{{Body}}}

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.

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 “McAdam”. If you used a sequential search method, you would open the phone book to the first page, then to the second page, continuing page by page until you have reached the M’s, and finally reach McAdam.

Is that realistic? No! You would flip to the middle of the book, check if M's are on the right, or the left, and continue cutting the book until you find the right page.

This is the idea of the binary search. Cut the array in half. Is the element contained in the right portion, or the left portion? Remove one half. Cut the remaining half in half. Is the element contained in the right portion, or the left portion? ... and we continue until our element is found (or we are out of bounds.)

E.g. search for “40”. 1) Note the position of the first element, last element, and middle element of the array.

2) Determine which range the element falls in: (10,30), or (30,50) – It’s in the (30,50) range. Recalculate our left/middle/right elements:

3) Continue this process until the desired element has been found, or the left/right pointers are out of bounds.

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;
		}
	}//end while
	return result;
}//end binarySearch()