Data Structures and Algorithms - Sorting and Searching
28. The average successful search time taken by binary search on a sorted array of 10 items is
- Option : D
- Explanation : The 10 items i1, i2, ..., i10 may be arranged in a binary search tree as in Fig To get i5, the number of comparison needed is 1; for i2, it is 2; for i8 it is 2; for i1 it is 3, and so on. The average is (1+(2+2) +(3+3+3+3)+(4+4+4))/10, i.e., 2.9.
29. The average successful search time for sequential search on 'n' items is
- Option : C
- Explanation : If the search key matches the very first item, with one comparison we can terminate. If it is second, two comparisons , etc. So, average is (1+2+...+n)/n .i.e. (n+1)/2
