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?

shivani @shivani1234
29 Apr 2017 12:42 pm
  • Since , it is already given that 0's are followed by 1's , so we can say array is sorted array.
  • We can apply binary search algorithm to find smallest index.
  • Let us consider worst case example 011111....1.
  • 1st probe : a1 a2 a3...a15  a16  a17 ... a31 // checks if a16 ==1, if so goes to  LHS of a16. ,  else if a16 ==0, it so goes to  RHS of a16. 
  • 2nd probe:  a1 a2 a3...a7  a8  a9...a15// assuming worst case happens , and we have to check again.
  • 3rd probe: a1 a2 a3  a4   a5 ..a7//assuming worst case happens , and we have to check again.
  • 4 th probe:a1 a2 a3//assuming worst case happens , and we have to check again.
  • 5th probe : RHS and LHS of a2 is  checked .
  • So , total 5 probes are required.
  • Optical algorithm: Using an algorithm that has less time complexity and space complexity for very very large inputs.
  • Example: Use of hashing technique, dictionary, sorting techniques of O(n),...


shweta @shweta1920
30 Apr 2017 01:32 am

great!!!!!!!!!!!!!!!!!!!!!!!!!.. thank u so much

Ashish Kumar Goyal @dashish
11 Oct 2018 02:39 pm

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 \left \lceil log(n) \right \rceil to get the solution.

Atanu Sarkar @atanusarkar
11 Oct 2018 11:06 am
great explanation .
Soumya Garg @soumyagarg
21 Jan 2019 07:22 pm
Why can't we take 0000...01 as worst case? In that case no. of comparisons will be 6.
Ashish Kumar Goyal @dashish
22 Jan 2019 07:01 pm

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