What is the
maximum/average number of sequential searches needed in finding
an element in a array?
The number of
searches required is dependent upon the number of elements in
the list.
The formula
to determine this is as follows:
The Maximum number of searches required is: (n+1)
The Average number of searches
required is: (n+1)/2
(Where n =
the number of elements on the list)
like I said,
the number of searches in a array required is dependent upon
the number of elements in the list. To illustrate:
No. of
Elements
Maximum No. of searches Avg. No. of
searches
5
6 3
50
51 25.5
500
501
250.5
5000
5001
2500.5
50000
50001 25000.5
If all elements are to be examined, a sequential search is
preferred over a binary search.
Some good
references are:
http://cis.stvincent.edu/carlsond/swdesign/arrays/arrays.html
A sequential
search is less complex and requires less comparisons than binary
searches.
Review
Questions:
1. What would
be maximum number of searches in an array containing 20
elements?
a)
19
b)
20
c)
21
d)
22
(Correct
answer is c)
2. What would
be the average number of searches for the same No. of elements
as question 1?
a)
10
b)
10.5
c)
11
d)
11.5
(Correct
answer is b)
3. In which
circumstance is sequential search preferred over binary search?
a)
When list contains more than 30 elements.
b)
When specific elements are sought.
c)
When all elements are to be examined.
(correct
answer is c)
4.how does a
sequential search differ from a binary search?
Answer:
sequential search is less complex and requires less comparisons.
CIS3355:
Business Data Structures