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 _________.
→ 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 = ceil(log2 31) = 4.954196310386876
⇒ here we are using ceiling so it becomes 5
It will run into an infinite loop when x is not in listA.
It is an implementation of binary search.
It will always find the maximum element in listA.
It will return −1 even when x is present in listA.
k = (i+j)/2;
where k keeps track of current middle element & i, j keeps track of left & right children of current subarray.
So it is an implementation of Binary search.
Optimal binary search tree construction can be performed efficiently using dynamic programming.
Breadth-first search cannot be used to find converted components of a graph.
Given the prefix and postfix walks over a binary tree, the binary tree cannot be uniquely constructed.
Depth-first search can be used to find connected components of a graph.