1. Which of the following is not an application of binary search?
a) To find the lower/upper bound in an ordered sequence
b) Union of intervals
c) Debugging
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.
2. Binary Search can be categorized into which of the following?
a) Brute Force technique
b) Divide and conquer
c) Greedy algorithm
d) Dynamic programming
Explanation: Since ‘mid’ is calculated for every iteration or recursion, we are diving the array into half and then try to solve the problem.
3. Given an array arr = {5,6,77,88,99} and key = 88; How many iterations are done until the element is found?
a) 1
b) 3
c) 4
d) 2
Explanation: Iteration1 : mid = 77; Iteration2 : mid = 88;
4. 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?
a) 90 and 99
b) 90 and 100
c) 89 and 94
d) 94 and 99
Explanation: Trace the input with the binary search iterative code.
5. What is the time complexity of binary search with iteration?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
Explanation: T(n) = T(n/2) + theta(1)
Using the divide and conquer master theorem, we get the time complexity as O(logn).
6. In which of the cases uniform binary search fails compared to binary search?
a) A table lookup is generally faster than an addition and a shift
b) Many searches will be performed on the same array
c) Many searches will be performed on several arrays of the same length
d) Complexity of code
Explanation: Uniform binary search code is more complex to implement than binary search as it involves mid points to be computed in hand before search.
7. Given delta[4] is a global array and number of elements in the sorted array is 10, what are the values in the delta array?
a) 4, 3, 1, 0
b) 5, 3, 1, 0
c) 4, 2, 1, 1
d) 5, 2, 1, 1
Explanation: Trace with respect to the make_delta function, always note that the last element is always 0.
8. What is the time complexity of uniform binary search?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
Explanation: With every iteration we are dividing the array into two parts(though not equal halves), the complexity remains same as the normal binary search.
9. Given, arr = {1,3,5,6,7,9,14,15,17,19} key = 17 and delta = {5,3,1,0}
How many key comparisons are made?(exclude the comparison used to decide the left or right sub array)
a) 4
b) 3
c) 5
d) 6
Explanation: Tracing with the above code, comparison #1: i=4, comparison #2: i=7, comparison #3: i=8
10. How can Jump Search be improved?
a) Start searching from the end
b) Begin from the kth item, where k is the step size
c) Cannot be improved
d) Step size should be other than sqrt(n)
Explanation: This gives a very slight improvement as you are skipping the first k elements.
Design and Analysis of Algorithms
The Grand Ball of Binary Search
Imagine you're at a grand masquerade ball, and you're searching for the one masked figure who holds the secret to your next adventure. Binary search is like Cinderella's glass slipper – it's precise, swift, and oh-so-charming.
In the magical land of algorithms, Binary Search reigns supreme for ordered lists. It's the fairy godmother of efficiency, ensuring you find your prince (or data) in the shortest time possible.
Dividing and Conquering Like a Pro
Binary Search is the ultimate master of the divide-and-conquer strategy. It's like slicing a magical cake into halves until you pinpoint the slice with the hidden treasure.
In the Design and Analysis of Algorithms carnival, Binary Search takes center stage when efficiency is the name of the game. It's the Gandalf guiding you through the perilous path of ordered datasets.
The Wizardry of Logarithms
Now, hold onto your wizard hats – here's the spell that makes Binary Search truly enchanting. Its time complexity is logarithmic, meaning it dances gracefully through large datasets without breaking a sweat.
In the land of MCQs in Design and Analysis of Algorithms, Binary Search is your magical wand. With its logarithmic prowess, it swiftly eliminates wrong answers, leaving you with the one true choice.
Wrapping It Up
In the fantastical world of algorithms, Binary Search is the spell that transforms chaos into order. Whether you're exploring enchanted forests or tackling MCQs in Design and Analysis of Algorithms, let Binary Search be your magical compass. May your code be efficient, your choices be wise, and your algorithms, enchanting! Happy coding, wizards of the algorithmic realm!