Searching

Topics in this chapter

• Linear Search Methods
• Binary Search Tracing
• Binary Search Order and Bounds
• Insertion and Duplicate Positions
• Search Complexity and Strategy
• Recursive and Iterative Search

Cheat sheet

Practice questions

1. Question 1Q-86E881

   What is printed by the following Python code? def linear_search(a, x): for i in range(len(a)): if a[i] == x: return i return -1 print(linear_search([14, 7, 21, 9], 21))

   1. A.1
   2. B.2
   3. C.3
   4. D.-1
   See the answer and solution
2. Question 2Q-02D2E3

   Consider the following binary search function and list: def binary_search(a, x): low, high = 0, len(a) - 1 while low <= high: mid = (low + high) // 2 if a[mid] == x: return mid elif a[mid] < x: low = mid + 1 else: high = mid - 1 return -1

   For a = [3, 8, 12, 17, 25, 31, 44, 50, 63] and x = 31, what are the returned index and the number of element comparisons made before finding the value?

   1. A.Index 5 and 2 comparisons
   2. B.Index 5 and 3 comparisons
   3. C.Index 4 and 3 comparisons
   4. D.Index 6 and 2 comparisons
   See the answer and solution
3. Question 3Q-37EDBE

   Why must the data be sorted before applying binary search? Also compare the worst-case time complexity of binary search with that of linear search.

   See the answer and solution
4. Question 4Q-0F94FB

   In an iterative linear search, what value is printed by the following Python code? def count_checks(a, x): checks = 0 for value in a: checks += 1 if value == x: break return checks print(count_checks([6, 1, 4, 9, 2], 9))

   1. A.3
   2. B.4
   3. C.5
   4. D.9
   See the answer and solution
5. Question 5Q-AE88AC

   In binary search on an ascending sorted list, what should be done when a[mid] is less than the target value x?

   1. A.Set high = mid - 1
   2. B.Set low = mid + 1
   3. C.Set low = mid - 1
   4. D.Stop the search because x is absent
   See the answer and solution