CIS3355:
Business Data Structures
Fall, 2008
|
|
|
What is a Sequential Search?
A sequential search is a search algorithm for searching a set of unsorted data for a particular value. A sequential search requires random access to the data being searched. It is the simplest basic search method. In sequential search we start from the beginning of the list, scan down the list, until the desired key is found or we have reached the end of the end of the list. More precisely, we define sequential search as: A = <a1, a2, a3, a4 ... an> be the list of n records, each record has a key element ai. Given a key value v, we can find the information or retrieve the record for the list, such that v = ai, i.e. we are finding the target record, by its key value. The basic formula for a sequential search is as follows: The Maximum number of searches required is n+1 (where n = the number of elements on the list) The Average number of searches required is (n+1)/2
Examples of a Sequential Search Ex.
Look at this array of integers:
Assume we wanted to find a particular element in this array ( e.g. 10):
Following the program through the for loop process: We can see that integer 10 was found at position 7.
Example 2 - Code for a simple Sequential Search
#include <iostream.h>
#include <apvector.h>
int main(void)
{
apvector <int> array(10);
//"drudge" filling the array
array[0]=20; array[1]=40; array[2]=100; array[3]=80; array[4]=10;
array[5]=60; array[6]=50; array[7]=90; array[8]=30; array[9]=70;
cout<< "Enter the number you want to find (from 10 to 100)…";
int key;
cin>> key;
int flag = 0; // set flag to off
for(int i=0; i<10; i++) // start to loop through the array
{
if (array[i] == key) // if match is found
{
flag = 1; // turn flag on
break ; // break out of for loop
}
}
if (flag) // if flag is TRUE (1)
{
cout<< "Your number is at subscript position " << i <<".\n";
}
else
{
cout<< "Sorry, I could not find your number in this array."<<endl<<endl;
}
return 0;
}
Example 3 - Code for a Sequential (Linear) Search. This is a very straightforward loop comparing every element in the array with the key. As soon as an equal value is found, it returns. If the loop finishes without finding a match, the search failed and -1 is returned. int linearSearch(int a[], int first, int last, int key) {
// function:
// Searches a[first]..a[last] for key.
// returns: index of the matching element if it finds key,
// otherwise -1.
// parameters:
// a in array of (possibly unsorted) values.
// first, last in lower and upper subscript bounds
// key in value to search for.
// returns:
// index of key, or -1 if key is not in the array.
for (int i=first; i<=last; i++) {
if (key == a[i]) {
return i;
}
}
return -1; // failed to find key
}
Questions: 1) A sequential search is also referred to as a: a) binary search b) static search c) linear search (Correct Answer) d) algorithm search 2) When will a sequential search end? - When the desired value is found, or when the end of the array is reached leaving no further information to search through. 3) In a sequential search the elements are reviewed: a) all at once b) a few at a time c) randomly d) one at a time (Correct Answer) 4) Where does the sequential search begin its search for the target integer? - Sequential searches begin at the first element of a list and will continue going through the list until the target element is found. 5) Can we deal with 0-based lists? 1-based lists? Correct Answer for 0-based / 1-based lists There is no problem with either… typically, the index of the first item depends on how the overlaying ADT is defined. Example: Linear lists typically start w/index 1. To convert to arrays, simply subtract one from the index to get an array slot. 6) Can we compare keys? How? Correct Answer for Comparing keys · If the keys are numbers, we can use the standard comparison operators. · If the keys are character strings, we need to use the strcmp( ) function. Strcmp(a,b) returns -1 if a < b, 0 if a and b are the same, +1 if a > b. · More complex keys typically require user-defined functions to compare. 7) Is a Binary Search preferred to a Sequential Search? Correct Answer · No, it depends on the situation and what action is to be taken or preformed: - If all elements are to be searched, then a sequential search is more beneficial. - A binary is only considered if the list contains 30-50 elements to be searched through.
8) Is there any way to reduce the number of required comparisons for sequential searches, if the list is not sorted? Correct Answer - No, if the list is not sorted, the comparisons can not be reduced. The only way for the comparisons in the search to be reduced is if the list were ordered in some manner that we new of. Otherwise the search must go on.
Conclusion
Searching is an important function in computer science and data structures.
Many advanced algorithms and data structures have been devised for the sole
purpose of making searches more efficient. And as the data sets become larger
and larger, good search algorithms will become more important. At one point in
the history of computing, sequential search was sufficient. But that quickly
changed as the value of computers became apparent. Additional Informational Links http://www.geocities.com/SiliconValley/Garage/3323/aat/a_seqs.html http://www.cs.sunysb.edu/~skiena/214/lectures/lect19/lect19.html http://www.cprogramming.com/discussionarticles/sorting_and_searching.html http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK4/NODE149.HTM http://download.cdsoft.co.uk/tutorials/sequentialsearch/ http://www.ics.uci.edu/~dan/class/161/notes/2/Sequential.html http://www.cs.xu.edu/csci170/05s/Algorithms/sequentialSearch.html http://mathbits.com/MathBits/CompSci/Arrays/Search.htm http://mathbits.com/MathBits/CompSci/Arrays/Search.htm http://kalpesh-patel.tripod.com/DS/Searching/index_sequential_searchSu.htm http://www.cis.ysu.edu/~kramer/DataStructures/Searching/SearchNotes.doc http://www.classes.cs.uchicago.edu/archive/2001/winter/CS106/html/lec13/sld005.htm http://www.mywiseowl.com/articles/Sequential_search http://pkirs.utep.edu/cis3355/Lecture%20Slides/CH9%20Searching%20and%20Sorting.ppt
Created by Gabriel Acosta, CIS 3355 The University of Texas at El Paso
|
