ITPEC FE Morning April 2022 Question 9

The data must be sorted — binary search compares the key with the middle element and discards the half that cannot contain it, which only works on ordered data.

Each step probes the middle of the remaining range. If the key is smaller, the search continues in the lower half; if larger, in the upper half. Deciding which half to discard depends on every element below the middle being smaller and every element above being larger, so the data must be sorted by the search key first.

Answer (c)

Why not others:

• •(a) — not always: a linear search finds an item in the first position in one comparison, and for very small data it can be just as fast
• •(b) — the search starts from the middle of the data; starting from the beginning is a linear search
• •(d) — log₂ N is only the bound of the worst case; a search can end at the first probe, so the count for a search is not proportional to log₂ N. The sorted-data condition holds for every binary search

Key rule: Binary search needs sorted data and takes at most about log₂ N + 1 comparisons, against up to N for a linear search.

Algorithm and Programming · AI-written, may contain errors