Searching · Class 12 · CBSE · Science Computer Science
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.
Practice question from Searching (Class 12 · CBSE · Science Computer Science), with the correct answer and a step-by-step solution.
hard · Subjective · Q-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.
Answer: Binary search requires sorted data so that, after comparing the target with the middle element, it can safely discard the half that cannot contain the target. Its worst-case time complexity is O(log n), whereas linear search checks elements one by one and has a worst-case time complexity of O(n).
Solution
Sorting provides the ordering needed to eliminate half of the remaining search range after each comparison. Consequently, binary search grows logarithmically with the number of elements, while linear search may inspect every element.
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…
- Consider the following binary search function and list: def binarysearch(a, x): low, high = 0, len(a) - 1 while low <= high: mid = (low + h…
- 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