Revision as of 15:21, 6 December 2011

COMP 1010 Home > More With Arrays > Searching Arrays

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:

• our search value has been found
• 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() 

Our linear search algorithm can be one step more efficient if our array is sorted in ascending order. Here is an example of an unsorted array, and that same array after being sorted. (We do not need to worry about sorting at this point, just imagine the array is sorted for you.)

 Unsorted array:      Sorted array: 

Using the sorted array above, if we were searching for the value "25", we would know after checking element 0 ("10"), element 1 ("20"), and then element 2 ("30"), that we will not find the value "25" since every element after element 2 will be greater than or equal to "30".

Furthermore, in 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 because "McAdams" must not be in the phone book.

A simple addition to our for loop will do the trick:

 searchValue >=list[counter] 

This completes our linear search 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() 

Let us sum up what we have covered. A linear search checks every element in an array in sequential order for a search value. The efficient linear search algorithm stops searching when: 1) we stop searching once our search value has been located, 2) our array is sorted in ascending order and we stop searching after a value is greater than our search value, or 3) we have reached the end of the array. A linear search, sometimes referred to as a sequential search, is not the best search to implement, but it is simple and does the trick.

Complete the review questions to apply your knowledge of linear searching.

Binary Search

A binary search is a step up from the linear search. We will revisit the telephone book example to see how the binary search works.

Example: find "McAdams" in the telephone book.
Let us recall how we searched for "McAdams" using the linear (sequential) search. We opened the phone book to the first page, then flipped to the second page, continuing page by page until reaching the M’s, and finally find McAdams, if it was in the phone book.

Is that realistic? No! What we would do is open to the middle of the phone book. Then we would check if M's are on the right, or the left of this page. If M was on the right, we would discard all the pages on the left and again cut this section in half, determine if M is on the right or left, and continue cutting and discarding the phone book until the correct page has been located.

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.

Now let us revisit our sorted array to see how a binary search would work. We are looking for “40” in this array: