Q.1 What is the primary requirement for applying binary search?
Array must be sorted
Array must be unsorted
Array must be rotated
Array must contain only positive numbers
Explanation - Binary search requires a sorted array because it works by dividing the search interval in half based on order.
Correct answer is: Array must be sorted
Q.2 What is the time complexity of binary search in the worst case?
O(1)
O(n)
O(log n)
O(n log n)
Explanation - Binary search halves the search space each time, leading to a worst-case complexity of O(log n).
Correct answer is: O(log n)
Q.3 In binary search, if the middle element is greater than the key, where do we continue the search?
Right half
Left half
Both halves
Stop searching
Explanation - If the key is smaller than the middle element, the search continues in the left half.
Correct answer is: Left half
Q.4 What is the best-case time complexity of binary search?
O(1)
O(n)
O(log n)
O(n/2)
Explanation - In the best case, the key matches the middle element on the first comparison.
Correct answer is: O(1)
Q.5 What is the space complexity of binary search (iterative version)?
O(n)
O(log n)
O(1)
O(n log n)
Explanation - Iterative binary search only requires a few variables for indices and does not use extra memory.
Correct answer is: O(1)
Q.6 Binary search is an example of which algorithmic paradigm?
Divide and Conquer
Dynamic Programming
Greedy
Backtracking
Explanation - Binary search applies the divide-and-conquer approach by reducing the problem size in half each time.
Correct answer is: Divide and Conquer
Q.7 On an array of 1024 elements, what is the maximum number of comparisons binary search may take?
512
1024
10
11
Explanation - Maximum comparisons = log2(1024) + 1 = 11.
Correct answer is: 11
Q.8 Binary search is applicable on?
Sorted arrays
Unsorted arrays
Graphs
Trees only
Explanation - Binary search can only be performed on sorted structures like arrays or lists.
Correct answer is: Sorted arrays
Q.9 What happens if binary search is applied to an unsorted array?
It works fine
It may return incorrect results
It will throw an error
It will sort the array first
Explanation - Binary search assumes order; applying it on unsorted arrays produces incorrect results.
Correct answer is: It may return incorrect results
Q.10 Which data structure is best suited for binary search?
Stack
Queue
Array
Linked List
Explanation - Random access is required for binary search, which is efficiently supported by arrays.
Correct answer is: Array
Q.11 What is the maximum number of iterations required in binary search for an array of size n?
n
n/2
log2(n)
n log n
Explanation - Binary search halves the size of the problem each time, leading to log2(n) iterations.
Correct answer is: log2(n)
Q.12 Which of the following is NOT true about binary search?
Works on sorted arrays
Has O(log n) time complexity
Requires random access
Works efficiently on linked lists
Explanation - Binary search is inefficient on linked lists because they lack random access.
Correct answer is: Works efficiently on linked lists
Q.13 In recursive binary search, what contributes to additional space complexity?
Array storage
Recursion stack
Sorting operation
Extra array creation
Explanation - Recursive binary search requires stack space proportional to log n for function calls.
Correct answer is: Recursion stack
Q.14 Binary search cannot be applied to which type of data?
Sorted integers
Sorted strings
Sorted linked list
Unsorted array
Explanation - Without sorting, binary search fails to locate elements correctly.
Correct answer is: Unsorted array
Q.15 What will binary search return if the element is not found?
-1
0
Array size
Null
Explanation - Typically, binary search returns -1 to indicate the absence of the element.
Correct answer is: -1
Q.16 In binary search, how is the mid index usually calculated to prevent overflow?
(low + high)/2
low + (high - low)/2
high/2
(low + high + 1)/2
Explanation - This formula avoids integer overflow when low and high are large.
Correct answer is: low + (high - low)/2
Q.17 What is the main disadvantage of binary search?
Slower than linear search
Requires sorted data
Consumes more memory
Cannot find duplicates
Explanation - The prerequisite of having sorted data is the main drawback of binary search.
Correct answer is: Requires sorted data
Q.18 Which of the following is an application of binary search?
Finding shortest path
Searching in phonebook
Hash table lookup
Sorting numbers
Explanation - Phonebooks are sorted, making binary search an efficient option.
Correct answer is: Searching in phonebook
Q.19 Which one is faster in average case: Binary Search or Linear Search?
Binary Search
Linear Search
Both same
Depends on array size
Explanation - Binary search reduces time complexity to O(log n), faster than linear search's O(n).
Correct answer is: Binary Search
Q.20 Binary search is efficient for arrays of what size?
Small arrays
Large arrays
One element array
Only prime-sized arrays
Explanation - For large arrays, binary search significantly reduces comparisons compared to linear search.
Correct answer is: Large arrays
Q.21 If an array has 1 million elements, maximum binary search steps are about?
10
20
30
40
Explanation - log2(1,000,000) ≈ 20 steps are sufficient to search.
Correct answer is: 20
Q.22 What is the advantage of iterative binary search over recursive binary search?
Uses less space
Runs faster
No sorting required
Works on unsorted data
Explanation - Iterative binary search avoids recursion overhead and stack usage.
Correct answer is: Uses less space
Q.23 In binary search, the search space reduces by what factor after each step?
1/2
1/3
1/4
2
Explanation - Each comparison halves the remaining search space.
Correct answer is: 1/2
Q.24 Binary search can be extended to work on which type of data besides arrays?
Graphs
Binary Search Trees
Hash Tables
Stacks
Explanation - BSTs allow binary search since elements are arranged in sorted order.
Correct answer is: Binary Search Trees
Q.25 If array size is odd, how is the mid element chosen in binary search?
Middle index
First index
Last index
Random index
Explanation - When size is odd, the exact middle index is chosen as mid.
Correct answer is: Middle index