# 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...