30 practice sets · Page 2 of 2
What is the time complexity of binary search with iteration?
O(nlogn)
O(logn)
O(n)
O(n^{2})
Correct Answer: B — O(logn)
Explanation:
(T(n) = T(n/2) + theta(1))
Using the divide and conquer master theorem, we get the time complexity as O(logn).
Given an array arr = {45,77,89,90,94,99,100} and key = 100; What are the mid values(corresponding array elements) generated in the first and second iterations?
90 and 99
90 and 100
89 and 94
94 and 99
Correct Answer: A — 90 and 99
Explanation:
Trace the input with the binary search iterative code.
Given an array arr = {5,6,77,88,99} and key = 88; How many iterations are done until the element is found?
1
3
4
2
Correct Answer: D — 2
Explanation:
Iteration1 : mid = 77; Iteration2 : mid = 88;
Binary Search can be categorized into which of the following?
Brute Force technique
Divide and conquer
Greedy algorithm
Dynamic programming
Correct Answer: B — Divide and conquer
Explanation:
Since 'mid' is calculated for every iteration or recursion, we are diving the array into half and then try to solve the problem.
Which of the following is not an application of binary search?
To find the lower/upper bound in an ordered sequence
Union of intervals
Debugging
To search in unordered list
Correct Answer: D — To search in unordered list
Explanation:
In Binary search, the elements in the list should be sorted. It is applicable only for ordered list. Hence Binary search in unordered list is not an application.
What is the average case time complexity of binary search using recursion?
O(nlogn)
O(logn)
O(n)
O(n^{2})
Correct Answer: B — O(logn)
Explanation:
T(n) = T(n/2) + 1, Using the divide and conquer master theorem.
What is the worst case complexity of binary search using recursion?
O(nlogn)
O(logn)
O(n)
O(n^{2})
Correct Answer: B — O(logn)
Explanation:
Using the divide and conquer master theorem.
Given an array arr = {45,77,89,90,94,99,100} and key = 99; what are the mid values(corresponding array elements) in the first and second levels of recursion?
90 and 99
90 and 94
89 and 99
89 and 94
Correct Answer: A — 90 and 99
Explanation:
At first level key = 90
At second level key= 99
Here 90 and 99 are mid values.
Given an input arr = {2,5,7,99,899}; key = 899; What is the level of recursion?
5
2
3
4
Correct Answer: C — 3
Explanation:
level 1: mid = 7
level 2: mid = 99
level 3: mid = 899(this is the key).
What is the advantage of recursive approach than an iterative approach?
Consumes less memory
Less code and easy to implement
Consumes more memory
More code has to be written
Correct Answer: B — Less code and easy to implement
Explanation:
A recursive approach is easier to understand and contains fewer lines of code.
