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

ID: 3595083 • Letter: C

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 value could have been. 2. Give an example sorted list of at least length 8, and a search value, where the number of comparisons would be the minimum possible number of comparisons. a. Use your example and a new search value to show where the number of comparisons is the worst case for the linear search (i.e. you have to look at every element in the list) b.

Explanation / Answer

2.a) Example: Suppose the sorted list of length 8 is : [ 3, 17, 22, 37, 41, 59, 65, 79 ]

And let the search value is 3;

For linear search, the search would start from the 1st element of the array; search value 3 would be compared with the 1st element of the list which is 3 here; as this comparison would give a true result, then the search would stop and return the index of 3.

Now the number of comparisons would be 1 and it is the minimum possible number of comparisons. If the search value is the 1st element of the list then only the number of comparison would be minimum.

2.b) Example: Suppose the sorted list of length 8 is : [ 3, 17, 22, 37, 41, 59, 65, 79 ]

And let the search value is 93;

For linear search, the search would start from the 1st element of the array; search value 93 would be compared with the 1st element of the list which is 3 here; as this comparison would give a false result, then the search element would be compared with the next element of the list and so on until a match is found; as the search value is not present in the list, it would be compared with every element of the list and then stop. Now the number of comparisons would be 8 and it is the maximum possible number of comparisons; it is the worst case scenario. If the search value is not present in the list then we have to look at every element in the list. Hence the number of comparison would be maximum.

/*If this helps you, please let me know by giving a positive thumbs up. In case you have any queries, do let me know. I will revert back to you. Thank you!!*/

Navigate

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

Consider a basket of consumer goods that costs $72.00 in the United States. The

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

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

Question

Explanation / Answer

Related Questions

Navigate