Revision as of 14:31, 3 December 2007

COMP 1010 Home > More With Arrays

{{{Body}}}

Review Questions

Passing Arrays using Methods

Working with Paritally Filled Arrays

Arrays of Strings

Searching Arrays

1. No, the array does not need to be sorted for a linear search, but it is more efficient if it is.
2. Yes, the array does need to be sorted for a binary search.
3. A binary search is more efficient.
4. The binary search.

Sorting Arrays

Parallel Arrays

Exercises

Apply the binary search

Question:
Modify the binarySearch() algorithm to keep count of how many elements the algorithm checks to find the desired element. Print out each checked element's value (in other words, the value compared with the search value.)

Solution:
First, to keep count of the number of elements checked, we must at a variable, count. This variable will be incremented (count++) each time we do a comparsion (three times.)

Secondly, to print each element checked, we can simply add a System.out.println() statement at the end of our while loop. For esthetics only, we also print out the count variable.

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)

        int count;              //# element checked during search

	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

        count = 0;              //we haven't checked any elements yet

	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;

                        count++;
		}

		else if (middleElement < searchValue)
		{//need to discard left portion of array
			left = middle + 1;

                        count++;
		}

		else if (middleElement > searchValue)
		{need to discard right portion of array
			right = middle – 1;

                        count++;
		}
 
                System.out.println("Value compared: " + middleElement);
                System.out.println("Number of elements counted: " + count);

	}//while
	return result;
}//binarySearch()