Data Structures u0026 Algorithms: Advanced Searching Techniques Quiz

Challenge your understanding of complex searching algorithms, including linear search, binary search variants, ternary search, and search in rotated arrays. This quiz tests in-depth concepts, edge cases, and algorithmic optimizations.

1. Time Complexity of Linear Search

   Given a sorted array of 1,000,000 unique integers, what is the worst-case time complexity of linear search when searching for the last element?

   1. O(log n)
   2. Ω(n^2)
   3. O(1)
   4. O(n)
   5. O(n log n)

2. Binary Search Precondition

   Which condition must be guaranteed for the standard binary search algorithm to function correctly on an array?

   1. Array indices must start at 1.
   2. The array contains only positive numbers.
   3. Each element must be unique.
   4. The array is unsorted.
   5. The array must be sorted in non-decreasing order.

3. Handling Duplicates in Binary Search

   You are tasked with finding the first occurrence of a target value in a sorted array containing duplicates; how should the standard binary search be modified?

   1. Stop immediately upon finding any occurrence.
   2. Continue searching the left half after finding the target.
   3. Search only the right half upon finding the target.
   4. Use a ternary search instead of binary search.
   5. Reverse the direction of search after each iteration.

4. Binary Search in Rotated Arrays

   Given a sorted array rotated at an unknown pivot (e.g., [4,5,6,7,0,1,2]), which strategy enables binary search to locate a target in O(log n) time?

   1. Locate pivot using linear search, then use binary search.
   2. Perform ternary search across the array.
   3. At each step, determine which half is sorted, then decide which half to search.
   4. Compare every pair of elements until the target is found.
   5. Always search the left half first, then the right if not found.

5. Ternary Search Best Use Case

   In which scenario is applying the ternary search algorithm more appropriate than using binary search?

   1. When searching for a particular value in an unsorted list.
   2. When the array has duplicate values.
   3. When all array elements are identical.
   4. When the array contains only two elements.
   5. When searching for the minimum or maximum of a unimodal function.

6. Lower Bound Binary Search Implementation

   When implementing lower_bound to find the first index where a value not less than a given key occurs in a sorted array, which loop condition is most appropriate?

   1. while (high u003C low)
   2. while (low u003C high)
   3. while (mid != n)
   4. while (low u003E high)
   5. while (low u003C= high)

7. Exponential Search Advantage

   Why might exponential search outperform binary search on infinite or unbounded sorted lists?

   1. It skips over all duplicates automatically.
   2. It uses constant space complexity.
   3. It quickly finds the range where the target may reside before binary search.
   4. It only requires a single comparison per iteration.
   5. It works without needing any sorted order.

8. Iterative vs. Recursive Binary Search

   Which is a primary benefit of iterative binary search compared to the recursive approach in most systems?

   1. It does not require additional space for function call stack.
   2. It can search unsorted arrays directly.
   3. It automatically handles duplicate elements.
   4. It always executes faster than recursion.
   5. It finds minimum and maximum simultaneously.

9. Edge Case: Binary Search Termination

   In a binary search implementation, which error can cause an infinite loop or stack overflow if not handled properly?

   1. Using '(low + high)/2' instead of 'low + (high - low)/2'.
   2. Sorting the array before calling binary search.
   3. Failing to update the lower or upper bounds when the condition matches.
   4. Forgetting to increment the search index.
   5. Not checking for out-of-bound values before starting.

10. Ternary vs. Binary Search: Time Complexity

    Compare the time complexities of binary search and ternary search when applied to a sorted array of n elements.

    1. Ternary search is O(log_3 n), while binary search is O(n!).
    2. Ternary search is always faster for any input size.
    3. Both have O(n^2) time in the worst case.
    4. Binary search: O(n), Ternary search: O(log n)
    5. Both achieve O(log n) time complexity asymptotically.