The GATE Grind

GATE 2017 CS – Question 58

Algorithms · Searching, Sorting and Hashing · 2 marks · Numerical answer

Let $A$ be an array of 31 numbers consisting of a sequence of 0's followed by a sequence of 1's. The problem is to find the smallest index $i$ such that $A[i]$ is 1 by probing the minimum number of locations in $A$. The *worst case* number of probes performed by an *optimal* algorithm is ________.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: 5

Explanation

The best method is binary search for the point where the 0s turn into 1s. Each probe halves the range, and 31 elements need at most $\lceil \log_2 32 \rceil = 5$ probes in the worst case.