Searching Algorithms Questions and Answers

Q: An array \(A\) of length \(n\) with distinct elements is said to be bitonic if there is an index \(1 \le i \le n\) such that \(A[1..i]\) is sorted in the non-decreasing order and \(A[i+1..n]\) is sorted in the non-increasing order.Which ONE of the following represents the best possible asymptotic bound for the worst-case number of comparisons by an algorithm that searches for an element in a bitonic array \(A\)?

The best bound is Θ(log n).A search in a bitonic array can be done in three binary searches:Find the peak, the index where the array stops increasing: compare A[mid] with A[mid + 1] and move towards the larger one. O(log n) comparisons.Binary search the increasing part A[1..peak].Binary search the decreasing part with the comparison reversed.That is O(log n) in all, and Ω(log n) is unavoidable because a sorted array is a special case of a bitonic one, and searching it needs log n comparisons. Θ(n) is a linear scan, Θ(1) is impossible, and Θ(log2 n) is what one gets by searching without first finding the peak, which is not optimal.

Q: The extra key inserted at the end of the array is called a/an :

The extra key is called a sentinel.In a sentinel search the value being looked for is placed in an extra position at the end of the array before a linear search starts. The loop can then compare elements with the key without also checking at every step whether the index has passed the end, because the search is certain to stop at the sentinel. If it stops there, the key was not in the original array.'End key' and 'stop key' are not the standard terms, and transposition is a self-organising search heuristic that swaps a found item with its predecessor.

Q: A technique for direct search is :

The direct search technique is Hashing.Hashing computes the storage address of a record directly from its key by a hash function, so in the ideal case the item is reached in one step, O(1), without comparing it with other keys.Linear search compares the key with items one by one, binary search halves a sorted list by comparison at each step, and tree search follows a path of comparisons from the root. All three are comparison-based searches rather than direct ones.

Q: Working modulo q = 11, how many spurious hits does the Rabin Karp matcher encounter in the text T = 459263781 when working for the pattern β = 37 :

The matcher encounters 4 spurious hits.The pattern's hash is 37 mod 11 = 4. Rabin-Karp compares this with the hash of every two-digit window of the text 459263781:455992266337788114448414Five windows hash to 4: 59, 92, 26, 37 and 81. Only 37 is a real match. The other four, 59, 92, 26 and 81, are spurious hits: their hash agrees with the pattern's but the digits do not.Counting the true match as well gives 5, which is the trap in option D.

Q: For binary search algorithm, which of the following is not a required condition ?

The condition that is not required is an easy mechanism to delete and/or insert elements.Binary search requires the list to be sorted and needs direct access to the middle element of any sublist, which is why it suits arrays and not linked lists.Ease of insertion and deletion is not needed to search; arrays make insertion costly and binary search still works on them. So options A and C are requirements, and 'None of the above' is wrong because B is not one.

Q: A binary search on a sorted array of n elements takes

Binary search takes O(log n) time.Each comparison with the middle element halves the part of the array that can still hold the target. Starting from n elements, after k comparisons at most n/2k remain, so the search ends after about log2 n steps: around 20 comparisons for a million elements.O(n) is linear search, which checks elements one by one. O(1) is direct indexing or an average hash-table lookup, and O(n2) is the cost of simple sorts such as bubble sort, not of searching a sorted array.

Q: Which of the following is true about the time complexity of the Binary Search algorithm ?

Binary search runs in O(logn) time.Each comparison halves the part of the sorted array still to be searched, so after k steps \(n/2^k\) elements remain, and the search ends after about \(\log_2 n\) steps.O(n) is linear search, O(n log n) is efficient sorting, and \(O(n^2)\) is simple sorting such as bubble sort.For example, a sorted array of a million elements needs at most about 20 comparisons.

Q: What is the time complexity of the binary search algorithm ?

Binary search takes O(log n) time.On a sorted array, each comparison with the middle element discards half of the remaining range. After k comparisons n/2k elements remain, so at most about log2 n comparisons are needed. A million elements need only about 20.O(1) would mean finding the item in one step whatever the size, which only hashing approaches. O(n) is linear search, and O(n log n) is the cost of sorting the array first.

Q: The increasing order of performance of the searching algorithms are

The increasing order is linear search \(\lt\) jump search \(\lt\) binary search.On a sorted list of n items, linear search takes O(n) comparisons, jump search (jumping ahead by about \(\sqrt{n}\) steps and then scanning back) takes O(\(\sqrt{n}\)), and binary search, halving the range each time, takes O(log n).Since \(\log n \lt \sqrt{n} \lt n\) for large n, performance improves from linear to jump to binary. The other options reverse one or both comparisons.

Q: The average number of key comparisons done in a successful sequential search in a list of length n is

The average is \((n+1)/2\).If the key is equally likely to be at any of the n positions, finding it at position i takes i comparisons, so the average is\[ \begin{aligned} \frac{1 + 2 + \cdots + n}{n} &= \frac{n(n+1)/2}{n} \\ &= \frac{n+1}{2} \end{aligned} \]n/2 and (n - 1)/2 are off by a half or one, and log n is the cost of binary search, not sequential search.In the worst case, when the key is last or absent, sequential search makes n comparisons.

An array \(A\) of length \(n\) with distinct elements is said to be bitonic if there is an index \(1 \le i \le n\) such that \(A[1..i]\) is sorted in the non-decreasing order and \(A[i+1..n]\) is sorted in the non-increasing order.

Which ONE of the following represents the best possible asymptotic bound for the worst-case number of comparisons by an algorithm that searches for an element in a bitonic array \(A\)?

A.\(\Theta(n)\)
B.\(\Theta(1)\)
C.\(\Theta(\log^{2} n)\)
D.\(\Theta(\log n)\)

Exam Year(s)

GATE CS - 2025,

Answer: D

The best bound is Θ(log n).

A search in a bitonic array can be done in three binary searches:

Find the peak, the index where the array stops increasing: compare A[mid] with A[mid + 1] and move towards the larger one. O(log n) comparisons.
Binary search the increasing part A[1..peak].
Binary search the decreasing part with the comparison reversed.

That is O(log n) in all, and Ω(log n) is unavoidable because a sorted array is a special case of a bitonic one, and searching it needs log n comparisons. Θ(n) is a linear scan, Θ(1) is impossible, and Θ(log² n) is what one gets by searching without first finding the peak, which is not optimal.

Discuss in Forum

The extra key inserted at the end of the array is called a/an :

A.End key
B.Stop key
C.Sentinel
D.Transposition

Exam Year(s)

MH SET - 2018, SET Exam - 2018,

Answer: C

The extra key is called a sentinel.

In a sentinel search the value being looked for is placed in an extra position at the end of the array before a linear search starts. The loop can then compare elements with the key without also checking at every step whether the index has passed the end, because the search is certain to stop at the sentinel. If it stops there, the key was not in the original array.

'End key' and 'stop key' are not the standard terms, and transposition is a self-organising search heuristic that swaps a found item with its predecessor.

Discuss in Forum

A technique for direct search is :

A.Linear search
B.Binary search
C.Hashing
D.Tree search

Exam Year(s)

MH SET - 2019, SET Exam - 2019,

Answer: C

The direct search technique is Hashing.

Hashing computes the storage address of a record directly from its key by a hash function, so in the ideal case the item is reached in one step, O(1), without comparing it with other keys.

Linear search compares the key with items one by one, binary search halves a sorted list by comparison at each step, and tree search follows a path of comparisons from the root. All three are comparison-based searches rather than direct ones.

Discuss in Forum

Working modulo q = 11, how many spurious hits does the Rabin Karp matcher encounter in the text T = 459263781 when working for the pattern β = 37 :

Exam Year(s)

MH SET - 2019, SET Exam - 2019,

Answer: C

The matcher encounters 4 spurious hits.

The pattern's hash is 37 mod 11 = 4. Rabin-Karp compares this with the hash of every two-digit window of the text 459263781:

45	59	92	26	63	37	78	81
1	4	4	4	8	4	1	4

Five windows hash to 4: 59, 92, 26, 37 and 81. Only 37 is a real match. The other four, 59, 92, 26 and 81, are spurious hits: their hash agrees with the pattern's but the digits do not.

Counting the true match as well gives 5, which is the trap in option D.

Discuss in Forum

For binary search algorithm, which of the following is not a required condition ?

A.The list must be sorted
B.There must be an easy mechanism to delete and/or insert elements in list
C.There should be a direct access to the middle element in any sublist
D.None of the above

Exam Year(s)

MH SET - 2024, SET Exam - 2024,

Answer: B

The condition that is not required is an easy mechanism to delete and/or insert elements.

Binary search requires the list to be sorted and needs direct access to the middle element of any sublist, which is why it suits arrays and not linked lists.

Ease of insertion and deletion is not needed to search; arrays make insertion costly and binary search still works on them. So options A and C are requirements, and 'None of the above' is wrong because B is not one.

Discuss in Forum

A binary search on a sorted array of n elements takes

A.O(n)
B.O(log n)
C.O(1)
D.\(O(n^{2})\)

Exam Year(s)

Tripura Public Service Commission - 2026,

Answer: B

Binary search takes O(log n) time.

Each comparison with the middle element halves the part of the array that can still hold the target. Starting from n elements, after k comparisons at most n/2^k remain, so the search ends after about log₂ n steps: around 20 comparisons for a million elements.

O(n) is linear search, which checks elements one by one. O(1) is direct indexing or an average hash-table lookup, and O(n²) is the cost of simple sorts such as bubble sort, not of searching a sorted array.

Discuss in Forum

Which of the following is true about the time complexity of the Binary Search algorithm ?

A.O(n)
B.O(logn)
C.O(nlogn)
D.O(n^2)

Exam Year(s)

Tripura Public Service Commission - 2025,

Answer: B

Binary search runs in O(logn) time.

Each comparison halves the part of the sorted array still to be searched, so after k steps \(n/2^k\) elements remain, and the search ends after about \(\log_2 n\) steps.

O(n) is linear search, O(n log n) is efficient sorting, and \(O(n^2)\) is simple sorting such as bubble sort.

For example, a sorted array of a million elements needs at most about 20 comparisons.

Discuss in Forum

What is the time complexity of the binary search algorithm ?

A.O(1)
B.O(log n)
C.O(n)
D.O(n log n)

Exam Year(s)

Tripura Public Service Commission - 2026,

Answer: B

Binary search takes O(log n) time.

On a sorted array, each comparison with the middle element discards half of the remaining range. After k comparisons n/2^k elements remain, so at most about log₂ n comparisons are needed. A million elements need only about 20.

O(1) would mean finding the item in one step whatever the size, which only hashing approaches. O(n) is linear search, and O(n log n) is the cost of sorting the array first.

Discuss in Forum

The increasing order of performance of the searching algorithms are

A.linear search \(\lt\) jump search \(\lt\) binary search
B.linear search \(\gt\) jump search \(\lt\) binary search
C.linear search \(\lt\) jump search \(\gt\) binary search
D.linear search \(\gt\) jump search \(\gt\) binary search

Exam Year(s)

Tripura Public Service Commission - 2025,

Answer: A

The increasing order is linear search \(\lt\) jump search \(\lt\) binary search.

On a sorted list of n items, linear search takes O(n) comparisons, jump search (jumping ahead by about \(\sqrt{n}\) steps and then scanning back) takes O(\(\sqrt{n}\)), and binary search, halving the range each time, takes O(log n).

Since \(\log n \lt \sqrt{n} \lt n\) for large n, performance improves from linear to jump to binary. The other options reverse one or both comparisons.

Discuss in Forum

10.

The average number of key comparisons done in a successful sequential search in a list of length n is

A.log n
B.(n - 1)/2
C.n/2
D.(n+1)/2

Exam Year(s)

Tripura Public Service Commission - 2025,

Answer: D

The average is \((n+1)/2\).

If the key is equally likely to be at any of the n positions, finding it at position i takes i comparisons, so the average is

\[ \begin{aligned} \frac{1 + 2 + \cdots + n}{n} &= \frac{n(n+1)/2}{n} \\ &= \frac{n+1}{2} \end{aligned} \]

n/2 and (n - 1)/2 are off by a half or one, and log n is the cost of binary search, not sequential search.

In the worst case, when the key is last or absent, sequential search makes n comparisons.

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Searching Algorithms Questions and Answers || Searching Algorithms MCQ Questions and Answers || Searching Algorithms GK Questions and Answers || Searching Algorithms GK MCQ Questions || Searching Algorithms Multiple Choice Questions and Answers || Searching Algorithms GK || GK on Searching Algorithms || Data Structures and Algorithms Questions and Answers || Data Structures and Algorithms MCQ Questions and Answers || Data Structures and Algorithms GK Questions and Answers || GK on Data Structures and Algorithms

Searching Algorithms Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications