Searching Arrays

COMP 1010 Home > Selection Search Algorithm

Introduction A common programming scenario involves searching an array for a particular value or key. (Placeholder)

{{{Body}}}

Selection Searching

Parallel arrays should be used whenever you need to create a list of items, but all the information you need to store will not fit into a single Primitive Data Type. For example, you need to to keep a list of people's names and addresses. A single array of Strings seperating the addresses from names with a comma might not practical, and difficult to implement. Using one array for names, and another array of equal size for addresses would be easier and more practical.

    
   String []names = new String[numberOfPeople];
   String []addresses = new String[numberOfPeople];

As you can see, setting up a set of parallel arrays is simply as easy as simply declaring two different arrays. Ensure that the arrays you wish to use in parallel are are created using the same length.

Binary Search

A binary search compared to a sequential search is much quicker. Consider this scenario: you are using a phone book to look up the name “McAdam”. Using a sequential search, you would flip 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, see if McAdam is 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()