Difference between revisions of "Searching Arrays"

From CompSciWiki
Jump to: navigation, search
Line 15: Line 15:
 
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.
 
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.
  
−
{{Template:1010Topic|Chapter_TOC=[[Parallel Arrays]]|Introduction=Parallel arrays are a predecesor of object arrays, which you will not be learning.(Placeholder)|Overview=This section will cover what parallel arrays are, what you can use them for, and how to create them.}}
 
  
−
Parallel arrays are an advanced use of arrays. Creation and use is fairly simple, and a natural step from creating and using simple arrays.
 
  
−
Parallel arrays should be used wherever you want to make a complex structure of similar or related data, but do not have the means.
+
==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.
  
−
==Parallel Array Creation==
+
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.) 
  
−
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]].  
+
E.g. search for “40”. 
−
For example, you need to to keep a list of people's names and addresses. A single array of [[String]]s 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.
+
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:
 
<pre>
 
<pre>
−
   
+
public static int binarySearch(int[] list, int searchValue)
−
  String []names = new String[numberOfPeople];
+
{
−
  String []addresses = new String[numberOfPeople];
+
int left;
 +
int right;
 +
int middle;
 +
int result;
 +
int middleElement;
  
−
</pre>
+
result = -1;
 +
left = 0;
 +
right = list.length-1;
  
−
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.
+
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()
 +
</pre>

Revision as of 11:30, 27 November 2007

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;
	int right;
	int middle;
	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()
Retrieved from "https://hci.cs.umanitoba.ca/mediawiki/index.php?title=Searching_Arrays&oldid=3849"