###### NTA UGC NET JUNE-2023 Paper-2

November 5, 2023###### Question 6973 – Computer-Graphics

November 5, 2023# Question 1797 – Nielit Scientist-B 17-12-2017

**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________**

Correct Answer: D

Question 8 Explanation:

→ If we apply binary search to find the first occurrence of 1 in the list, it will give us the smallest index i where 1 is stored.

→ As in this array sequence of 0’s is followed by sequence of 1’s, the array is sorted. We can apply binary search directly without sorting it.

→ So number of probes = ⌈(log

= ⌈4.954196310386876⌉

⇒5

→ As in this array sequence of 0’s is followed by sequence of 1’s, the array is sorted. We can apply binary search directly without sorting it.

→ So number of probes = ⌈(log

_{2}31)⌉= ⌈4.954196310386876⌉

⇒5

2

4

3

5

Subscribe

Login

0 Comments