a

1. Binary search is a more specialized algorithm than sequential search as it takes advantage of data that has been
a. Sorted
b. Not Sorted
c. random
d. none of the above
Ans:a
2. The underlying idea of binary search is to divide the sorted data into two halves and to examine the data at the point of the split. True.

3. Binary search when compared to linear search is
a. More efficient
b. Less efficient
c. slower
d. none
Ans:a

4. A search algorithm is an algorithm that accepts an argument a and tries to find a record in the file with the primary key as a. True.

5. Binary search is a part of or used in which of the following
a. binary insertion sort
b. ideal search
c. suffix array
d. all the above
Ans:d

6. Binary search is a kind of ________________ .
Ans. dichotomic search

7. _________________ strategy is a part of or used in binary search.
Ans. Divide and conquer

8. The run time of binary search is _______
a. O(ln n)
b. O(n ln n)
c. O(log n)
d. O(n)
Ans. a
The run time of binary search is O(ln n) which is log n to the base e.

9. For finding the middle element in a binary search to avoid overflows the formula used is __________ where high and low are non-negative.
Ans. mid = low + (high-low)/2

10. The mid element of a binary search can be found by using the relation ________________ .
Ans. mid = (high + low)/2

11. The average successful search time taken by binary search on a sorted array of 10 items is _____
a. 2.6
b. 2.7
c. 2.8
d. 2.9
Ans. d
The items I1,I2,….I10 may be arranged in a binary search tree as shown below.So,to match I5,the number of comparisons needed is 1;for I2,it is 2, for I8 it is 2,for I1 it is 3 and so on.So,the average is (1+(2+2)+(3+3+3+3)+(4+4+4))/10 = 2.9



















12. A fast way to search a sorted array is to use a __________.
Ans. Binary search

13. For an array of million items,________ search operation is better than _____________ search.
a. linear,binary
b. binary,linear
c. linear,fibonacci
d. none of the above
Ans. b
For an array of a million elements, binary search, O(log N), will find the target element with a worst case of only 20 comparisons. Linear search, O(N), on average will take 500,000 comparisons to find the element.

14. In case of a binary search,the array must be __________ before it is searched.
Ans. sorted

15. Which of the following statement(s) is/are not correct?
a. In sequential search, the time complexity of an unsuccessful search is O(N).
b.The average case time complexity of sequential search algorithm is O(N). . c. In binary search,an unsuccessful search requires examining every in the array
d. In Binary search, the time complexity of a successful search in the worst case is O(log N).
Ans. c

16. Consider the following algorithm.
(i) Compare the given Name with the Name in the middle of the list
(ii) This tells which half of the list contains Name
(iii) Then compare Name with the Name in the middle of the correct half to Determine which quarter of the list contains Name
(iv) Continue the process until finding Name in the list
What does the above algorithm describe?
a. Sequential search
b. Index sequential search
c. Merge sort
d. Binary search
Ans. d