Difference between revisions of "Searching Arrays"

Latest revision as of 03:27, 8 December 2011

COMP 1010 Home > More With Arrays > Searching Arrays

Introduction

We learned how to create arrays and you should know that an Array is a type of list that can contain one type of object. There will be situations where you will be a need to search for a particular value in an array. Today there are many algorithms to solve this problem. These algorithms have different inefficiencies which are measured as a "time complexity". In this Chapter we are going to discuss two search algorithms; Linear Search and Binary Search. Linear search is a brute force approach and Binary Search utilizes the middle index as a lower or upper bound for its search.

Linear Search

A linear search can be used to locate a value in an array. A linear search checks each element one after another (from left to right or right to left) 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:                              

|10|30|60|40|20|     

Sorted array:

|10|20|30|40|60| 

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) our search value has been located, 2) we have reached a value which 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:

 |10|20|30|40|60| 

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. We are left with the array below.

 |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 index 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;             //element that searchValue was found in
	int middleElement;      //middle value (comparing)

	result = -1;            //return -1 if searchValue is not found
	left = 0;               //left index starts at the first element
	right = list.length-1;  //right index starts at the last element

	while ((left <= right) && (result == -1))   //left and right boundaries do not overlap and searchValue is not found
	{
		middle = (left + right) / 2;
		middleElement = list[middle];

		if (middleElement == searchValue)   //we have found our searchValue
		{
			result = middle;
		}
		else if (middleElement < searchValue)   //need to discard left portion of array
		{
			left = middle + 1;
		}
		else if (middleElement > searchValue)   //need to discard right portion of array
		{
			right = middle – 1;
		}
	}//while
	return result;
}//binarySearch() 

Let us recap what we have learned about the binary search. A binary search is more efficient than a linear search. By comparing the array's middle value with the search value, we eliminate half the array and reduce the amount of numbers to be compared.

Complete the review questions to apply your knowledge of binary searching. Also, complete the Apply the Binary Search exercise for more practice.

Section Summary

To recap this section. In this section we learned two search algorithms, Linear search and Binary search. The two search algorithm are providing a good method to search for and element in the array. Out of the two algorithms Binary search is more efficient then linear search by having smaller time complexity. In this section we brought an example with Integers array but this search methods can be adapted to search any type of object. Please note that this topic is covered briefly, the further explanation will be provided in the COMP 1020 courses where algorithms and arrays will be discussed further