-
Let A be an array of 31 numbers consisting of a sequence of 0’s followed by a sequence of l’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 _____.
-
- 3
- 5
- 7
- 11
Correct Option: B
To find out the smallest index i such that A[i] is 1 by probing the minimum number of location in A. Assume i be the index of first element and j be the index of last element.
By using the binary search algorithm with some changes.
Now,
| Find middle element of Array = A |  |  | ||
| 2 |
Assuming ‘A’ is an array of 31 elements with ‘1’ and if it is ‘1’, we check the left part recursively and if it is ‘0’, we check the right part of the array recursively. Which take log2 (31) comparisons in the worst case, so the total worst case probes is
⇒ Ceil (log2 31) = 5
(∵ Ceil means compute fast log base 2 ceiling) 5 probes performed by an optimal algorithm.
