Searching · Class 12 · CBSE · Science Computer Science
Consider the following binary search function and list: def binarysearch(a, x): low, high = 0, len(a) - 1 while low <= high: mid = (low + high) // 2…
Practice question from Searching (Class 12 · CBSE · Science Computer Science), with the correct answer and a step-by-step solution.
medium · MCQ · Q-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?
- A.Index 5 and 2 comparisons
- B.Index 5 and 3 comparisonsCorrect answer
- C.Index 4 and 3 comparisons
- D.Index 6 and 2 comparisons
Solution
The middle positions checked are 4, 6, and 5, containing 25, 44, and 31 respectively. Thus, 31 is found at index 5 after 3 element comparisons.
More from Searching
- What is printed by the following Python code? def linearsearch(a, x): for i in range(len(a)): if a[i] == x: return i return -1 print(linear…
- Why must the data be sorted before applying binary search? Also compare the worst-case time complexity of binary search with that of linear…
- In an iterative linear search, what value is printed by the following Python code? def countchecks(a, x): checks = 0 for value in a: checks…
- In binary search on an ascending sorted list, what should be done when a[mid] is less than the target value x?
Practise more Computer Science
Sign up free for adaptive practice on this chapter, with instant feedback and hints on every question.
Start practising freeFree to start · No credit card needed