## Searching

Question 1 |

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 _________.

5 | |

6 | |

7 | |

8 |

→ 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(log

_{2}31) = 4.954196310386876

⇒ here we are using ceiling so it becomes 5

Question 2 |

Consider the C function given below. Assume that the array listA contains n (> 0) elements, sorted in ascending order.

int ProcessArray(int *listA, int x, int n) { int i, j, k; i = 0; j = n-1; do { k = (i+j)/2; if (x <= listA[k]) j = k-1; if (listA[k] <= x) i = k+1; } while (i <= j); if (listA[k] == x) return(k); else return -1; }

Which one of the following statements about the function ProcessArray is CORRECT?

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.

Question 3 |

Consider the following algorithm for searching for a given number x in an unsorted array A[1...n] having n distinct values:

1. Choose an i uniformly at random from 1...n; 2. If A[i]=x then Stop else Goto 1;

Assuming that x is present in A, what is the expected number of comparisons made by the algorithm before it terminates?

n | |

n-1 | |

2n | |

n/2 |

Question 4 |

Which one of the following statements is false?

Optimal binary search tree construction can be performed efficiently using dynamic programming. | |

Breadth-first search cannot be used to find connected 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. |

Question 5 |

**The time taken by binary search algorithm to search a key in a sorted array of n elements is**

O ( log _{2}n ) | |

O ( n ) | |

O ( n log _{2}n ) | |

O ( n _{2} ) |

Question 6 |

T(n)=2T(n/2)+k , where k is constant | |

T(n)=T(n/2) +k, where k is constant | |

T(n)=T(n/2)+logn | |

T(n)=T(n/2)+n |

__Binary search in a sorted array__

The time to search in an array of ‘n’ elements is equal to the time to search in an array of n/2 elements plus k comparison.

T(n)=T(n/2)+k // k is constant

Question 7 |

**The time required to search an element in a linked list of length n is**

O(log n) | |

O(n) | |

O(1) | |

(n ^{2}) |