Q.Estimate the number of key comparisons required in binary search and linear search if we need to find the details of a person in a sorted database having 2^30 (1,073,741,824) records when details of the person being searched lies at the middle position in the database. What do you interpret from your findings?

Binary search's very first probe is mid = (0 + (2³⁰ − 1)) // 2, which is precisely the middle position — an instant hit. Linear search has no idea the list is sorted, so it must compare every record from index 0 up to the middle: about half of 1,073,741,824 records. …

Concept understanding

The two techniques differ in the information they exploit.

• Linear search assumes nothing about the order of the records. Its only strategy is to compare the key with record 1, record 2, record 3, … until it matches. Its cost is proportional to the position of the target.
• Binary search exploits the fact that the records are sorted. It compares the key with the middle record; that single comparison tells it which half the key must lie in, and the other half — half a billion records — is discarded untouched.

The question chooses the target position deliberately: the middle. That is simultaneously binary search's best case and roughly linear search's average case, which makes the contrast as sharp as it can be.

Binary search — the count

Binary search needs 1 key comparison.

Linear search — the count

Linear search compares the key against record 1, then record 2, and so on, stopping only when it reaches the target. The target is the middle record, i.e. the (n/2)-th record.

Linear search needs about 536.87 million key comparisons.

Side-by-side

Why binary search's worst case is only 30

Each comparison halves the number of surviving records:

After 30 halvings only one record remains, so 30 comparisons settle any search in a billion-record sorted database.

Verifying with a program

import math

n = 2 ** 30                      # 1,073,741,824 records

linear_comparisons = n // 2      # key lies at the middle position
binary_comparisons = 1           # binary search probes the middle first
binary_worst_case = math.ceil(math.log2(n))

print('Records in database         :', n)
print('Linear search comparisons   :', linear_comparisons)
print('Binary search comparisons   :', binary_comparisons)
print('Binary search worst case    :', binary_worst_case)
print('Speed-up factor             :', linear_comparisons // binary_comparisons)

Output

Records in database         : 1073741824
Linear search comparisons   : 536870912
Binary search comparisons   : 1
Binary search worst case    : 30
Speed-up factor             : 536870912
``` …