Chapter 10: Searching

Question 1

On average, how many comparisons are required in a linear search of n elements?

Solution

The average number of comparisons in linear search will be as follows. When a search element is found at the 1^st position, 2^nd position, 3^rd position, and similarly at the n^th position, correspondingly, it will require 1, 2, 3… n number of comparisons.

Total average number of comparisons

=

=

=

Question 2

Assume there are eight elements in a sorted array. What is the average number of comparisons that will be required if all the searches are successful and if the binary search algorithm is used?

Solution

Average number of comparisons = (1+2+2+3+3+3+3+4)/8

= 21/8

= 2.625

Figure A.12: Demonstration of number of the comparisons in the given array

Question 3

What is the worst-case time complexity of the binary search algorithm?

Solution

O(logn).

The worst-case scenario of the...