Searching Arrays

COMP 1010 Home > Selection Search Algorithm

Introduction Now 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 an 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. This section will explain what these two search algorithms are, and how to implement them.

{{{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()

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:
|10|30|60|40|20|     |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) 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.

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

A binary search is a step up from the linear search. To help understand how the binary search works, let us revisit our telephone book example.

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 the phone book and discarding 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.

           |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;             //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 much more efficient than a linear search. If we compare the middle value of an array with our search value, this comparision will eliminate half the array, reducing the amount of numbers needing to be compared.