Consider a basic, linear search. In a linear search of a sorted data set, you ju

Question

Consider a basic, linear search. In a linear search of a sorted data set, you just examine each element, from the beginning of the list, one at a time, until you either find your value or realize it isn't there- you run out of data, or you go past the spot where the vaule could have been.

a. Give an example sorted list of at least length 8, and a search alue, where the number of comparisons would be the minimum possible number of comparisons.

b. Use your example and a new search value tos how where the number of comparisons is the worse case for the linear search (i.e. you have to look at every element in the list).

Explanation / Answer

For the list 2 4 6 8 10 12 14 16 18 20
a) For the search value 2, the comparisons will be the minimum.. as soon as we compare the first element of the list, we will find the desired element and we can stop the seach there itself.. Hence the Best Case.

b) For search value 20, We will start with the left end and one by one compare each and every element towards right till we find the desired element.. When we find 20, till the time, we have looked at every element in the list.. hence it is the worst case.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.