##### The worst case number of probes performed by an optimal algorithm

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 ii 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 ____________.

also what is optimal algorithm?

a16a17 ... a31 // checks if a16 ==1, if so goes to LHS of a16. , else if a16 ==0, it so goes to RHS of a16.a8a9...a15// assuming worst case happens , and we have to check again.a4a5 ..a7//assuming worst case happens , and we have to check again.a2a3//assuming worst case happens , and we have to check again.are required.5 probesgreat!!!!!!!!!!!!!!!!!!!!!!!!!.. thank u so much

nice illustration! One should have this type of understanding of all algorithms, However in exam, if the concept is clear, then u can directly use to get the solution.

why 6? check this using binary search, we would be looking in this sequence-> a16,a24,a28,a29,a30 =>

5 comparisons.