PRACTICE • LEARN • GROW
Searching MCQs
Solve topic-wise placement questions and improve your skills.
Searching Progress
0 of 34 completed
0%
Topic Track
You are viewing MCQs in preview mode. Log in to select options, submit answers, and track your progress.
Log In to Answer
1
What is the worst-case time complexity of Binary Search on a sorted array of size N?
A.
O(log N)
B.
O(1)
C.
O(N)
D.
O(N log N)
Explanation & Key
Correct Answer:
2
Which condition MUST be satisfied before applying standard Binary Search on an array?
A.
The array size must be a power of 2
B.
The array must be sorted or monotonic with respect to the search condition
C.
All elements must be positive distinct integers
D.
The array must be implemented as a linked list
Explanation & Key
Correct Answer:
3
In binary search implementations, why is `mid = low + (high - low) / 2` preferred over `mid = (low + high) / 2`?
A.
It executes in fewer CPU clock cycles
B.
It works on floating-point numbers
C.
It prevents integer overflow when low + high exceeds the maximum integer limit
D.
It allows binary search on unsorted arrays
Explanation & Key
Correct Answer:
4
What does the `std::lower_bound` function return in C++ STL for a sorted array?
A.
Iterator to the first element that is strictly greater than the target
B.
Iterator to the last element equal to the target
C.
Iterator to the smallest element in the array
D.
Iterator to the first element that is greater than or equal to the target
Explanation & Key
Correct Answer:
5
What does `std::upper_bound` return for target X in a sorted array?
A.
The first element that is strictly greater than X
B.
The first element that is greater than or equal to X
C.
The last element smaller than X
D.
The index of X rounded upwards
Explanation & Key
Correct Answer:
6
What is the average time complexity of Interpolation Search on uniformly distributed sorted data?
A.
O(log N)
B.
O(log(log N))
C.
O(1)
D.
O(N)
Explanation & Key
Correct Answer:
7
Under what condition does Interpolation Search degrade to O(N) worst-case time?
A.
When all elements are negative
B.
When the array size is a power of 2
C.
When elements grow exponentially or have heavily skewed distributions
D.
When the target element is located at the center
Explanation & Key
Correct Answer:
8
What is the time complexity of searching an element in a sorted rotated array of size N with unique elements?
A.
O(N)
B.
O(N log N)
C.
O(1)
D.
O(log N)
Explanation & Key
Correct Answer:
9
What is the worst-case time complexity of searching in a rotated sorted array containing duplicate elements?
A.
O(N)
B.
O(log N)
C.
O(N^2)
D.
O(1)
Explanation & Key
Correct Answer:
10
What is Exponential Search particularly useful for?
A.
Unsorted circular linked lists
B.
Unbounded or infinite arrays where the size is not known in advance
C.
Graphs with negative cycle weights
D.
Direct memory access in hardware caches
Explanation & Key
Correct Answer:
11
What is the time complexity of finding the peak element in an array where arr[i] > arr[i-1] and arr[i] > arr[i+1]?
A.
O(N)
B.
O(N log N)
C.
O(log N)
D.
O(1)
Explanation & Key
Correct Answer:
12
How many comparisons are required in Ternary Search in the worst case to search in an array of size N?
A.
log2(N)
B.
3 * log2(N)
C.
N / 3
D.
2 * log3(N)
Explanation & Key
Correct Answer:
13
When is Ternary Search used instead of Binary Search?
A.
To find the maximum or minimum of a unimodal function
B.
To search in unsorted linked lists
C.
To reverse arrays in-place
D.
To balance an AVL tree
Explanation & Key
Correct Answer:
14
In an N x M matrix where every row and column is sorted in ascending order, what is the optimal search time for target X?
A.
O(N * M)
B.
O(N + M)
C.
O(N log M)
D.
O(log(N + M))
Explanation & Key
Correct Answer:
15
What is the optimal time complexity to find the median of two sorted arrays of sizes M and N?
A.
O(M + N)
B.
O(log(M + N))
C.
O(log(min(M, N)))
D.
O((M + N) log(M + N))
Explanation & Key
Correct Answer:
16
What is the time complexity of finding the square root of integer N using binary search?
A.
O(N)
B.
O(1)
C.
O(sqrt(N))
D.
O(log N)
Explanation & Key
Correct Answer:
17
Which search algorithm requires that the items can be compared and indexed, and operates in O(sqrt(N)) time blocks?
A.
Jump Search
B.
Linear Search
C.
Binary Search
D.
Fibonacci Search
Explanation & Key
Correct Answer:
18
What is Fibonacci Search based on?
A.
Matrix exponentiation
B.
Divide and conquer using Fibonacci numbers to partition arrays with addition and subtraction only
C.
Dynamic programming memoization table
D.
Greedy knapsack selection
Explanation & Key
Correct Answer:
19
In the "Allocate Minimum Number of Pages" / "Painter Partition" problem, what technique is applied?
A.
Breadth-First Search on a Grid
B.
Topological Sort with Kahn Algorithm
C.
Binary Search on the Answer Space
D.
Suffix Array scanning
Explanation & Key
Correct Answer:
20
What is the best-case time complexity of Linear Search in an array of size N?
A.
O(log N)
B.
O(N)
C.
O(N/2)
D.
O(1)
Explanation & Key
Correct Answer:
21
Why does calculating midpoint as `mid = (lo + hi) / 2` cause bugs in Java and C++ for large arrays?
A.
Division by 2 is slow on modern CPUs
B.
The sum `lo + hi` can overflow signed 32-bit integer limit (2^31 - 1), resulting in a negative number and segmentation fault
C.
Floating point rounding errors occur
D.
It fails when lo is 0
Explanation & Key
Correct Answer:
22
What is Ternary Search and what type of functions is it used for?
A.
Searching a 3D array in O(n^3)
B.
A divide-and-conquer algorithm that divides search space into 3 parts, used to find the maximum or minimum of a unimodal function
C.
A search algorithm for ternary trees
D.
A binary search that makes 3 comparisons per step
Explanation & Key
Correct Answer:
23
What does `std::lower_bound` in C++ return when the target element is NOT present in the sorted vector?
A.
An iterator to `nums.end()`
B.
An iterator to the first element that is strictly GREATER than target
C.
nullptr
D.
An iterator to the smallest element in the vector
Explanation & Key
Correct Answer:
24
In Binary Search, how many comparisons are required in the worst case for an array of size n = 1,000,000?
A.
1,000,000
B.
500,000
C.
At most 20 comparisons (ceil(log_2(1,000,000)) = 20)
D.
100
Explanation & Key
Correct Answer:
25
What is Exponential Search (Galloping Search)?
A.
A search that takes exponential O(2^n) time
B.
Finding a range [2^(k-1), 2^k] where target resides by doubling indices, then performing binary search within that range
C.
Searching floating point exponents
D.
Searching an exponential distribution
Explanation & Key
Correct Answer:
26
What is Interpolation Search, and what is its average time complexity on uniformly distributed sorted data?
A.
O(log n)
B.
O(log(log n))
C.
O(n)
D.
O(1)
Explanation & Key
Correct Answer:
27
In an array sorted in ascending order and then rotated, how can you find the minimum element in O(log n) time?
A.
Linear scan
B.
Binary search: if nums[mid] > nums[hi], min is in right half (lo = mid + 1); otherwise min is in left half including mid (hi = mid)
C.
Sort the array again
D.
Check nums[0] and nums[n-1]
Explanation & Key
Correct Answer:
28
What is the invariant condition for the two-pointer binary search template `while (lo < hi)` vs `while (lo <= hi)`?
A.
`lo <= hi` is used when the search space is inclusive [lo, hi] and mid can be the answer; `lo < hi` is used for boundary convergence [lo, hi)
B.
They are identical and always interchangeable without logic changes
C.
`lo < hi` causes an infinite loop
D.
`lo <= hi` only works on even-sized arrays
Explanation & Key
Correct Answer:
29
Can Binary Search be applied on an unsorted array?
A.
Yes, always
B.
No, unless the array can be mapped to a monotonic boolean condition or specific peak-finding property
C.
Only if the array contains no negative numbers
D.
Only if all numbers are distinct
Explanation & Key
Correct Answer:
30
In the "Median of Two Sorted Arrays" problem, what is the optimal time complexity achievable using binary search partition?
A.
O(m + n)
B.
O(log(min(m, n)))
C.
O((m + n) log(m + n))
D.
O(log(m) * log(n))
Explanation & Key
Correct Answer:
31
What is the time complexity of searching an element in an m x n 2D matrix where each row and column is sorted in ascending order?
A.
O(m * n)
B.
O(m + n) by starting at the top-right corner
C.
O(log(m * n))
D.
O(1)
Explanation & Key
Correct Answer:
32
What does Linear Search do when encountering multiple copies of the target in an unsorted array?
A.
It always returns all occurrences simultaneously
B.
It returns the first occurrence encountered during the sequential scan from index 0
C.
It throws a runtime error
D.
It sorts the array first
Explanation & Key
Correct Answer:
33
In Binary Search, what does bitwise shift `mid = (lo + hi) >> 1` accomplish?
A.
Multiplies by 2
B.
Performs integer floor division by 2 at high CPU speed
C.
Reverses bits of mid
D.
Checks if number is even
Explanation & Key
Correct Answer:
34
When searching for the first element satisfying predicate P(x) = True in domain [1...10^18], why is binary search optimal?
A.
Because log_2(10^18) is only ~60 comparisons, finding the answer almost instantly
B.
Because linear search would run out of stack space
C.
Because 10^18 numbers can fit in CPU registers
D.
Because P(x) is always linear
Explanation & Key
Correct Answer:
Question Palette
Answered
Current
Not Attempted
Wrong
