Searching Algorithms Questions and Answers

Answer: D

The best bound is Θ(log n).

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

1. 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.
2. Binary search the increasing part A[1..peak].
3. 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.

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.

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.

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:

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.

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.