CIS3355:
Business Data Structures
Fall, 2008
|
|
|
What is a sequential search and what is an example of one?
The sequential search (sometimes called a linear search) is the simplest type of search, it is used when a list of integers is not in any order. It examines the first element in the list and then examines each "sequential" element in the list until a match is found. This match could be a desired work that you are searching for, or the minimum number in the list. It is important to remember that the: - maximum number of searches required is: n+1 - average number of searches required is: (n+1)/2 (n = the number of elements on the list) Sequential Search Example: We start by searching for the target at the first element in the list and then proceed to examine each element in the order in which they appear. Suppose we are looking for the character "4." (keep in mind this is a simple diagram to help you understand the basics)
Once the target item has been found, a Boolean true, or the index where it was found, is returned. A couple of good references can be found at: http://www.sparknotes.com/cs/searching/linearsearch/section1.html http://www.lcusd.net/lchs/dclausen/apcs_cpp/PowerPoint/sequentialsearchch8vectors/sld002.htm http://www.cse.ucsc.edu/classes/cmps012b/Spring97/Lecture11/sld009.htm Now some questions: 1) A sequential search is also referred to as a: a) binary search b) static search c) linear search d) algorithm search (ANSWER: C) 2) 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 (ANSWER: D) 3) When will a sequential search end? (ANSWER: When the desired value is found, OR when the end of the array is reached) 4) Where does the sequential search begin its search for the target integer? (ANSWER: The sequential search begins at the first element of the list and continues until it reaches the target integer.)
|
