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 ________.
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.
More Searching, Sorting and Hashing questions
GATE 2014 CS (CS1) Q24– Quicksort P sorts ascending using the first element as pivot. Let t₁ and t₂ count its…
GATE 2014 CS (CS1) Q49– Find the minimum comparisons needed to find both minimum and maximum of 100 numbers.
GATE 2014 CS (CS3) Q24– Quicksort on n array elements always chooses the central array element as pivot. Find the…
GATE 2014 CS (CS3) Q52– listA contains n > 0 elements sorted in ascending order. Which statement about…
GATE 2016 CS (CS2) Q23– Algorithms sort in ascending order. On an already ascending input, which are true? I:…
GATE 2013 CS Q16– What is the tightest upper bound on swaps used by selection sort on n numbers?