Practice question · True or false
Binary search is O(log n), so searching an unsorted array once is faster if you sort it first.
Hints
- What does sorting cost?
- Compare O(n log n) + O(log n) against a single O(n) scan.
Show the answer
False
Why
False. Sorting costs O(n log n), which is worse than the O(n) linear scan it saves, for a single search, scanning wins. Sorting pays off when the array is searched many times: k searches cost O(n log n + k log n) against O(kn), and the crossover is early.
Practise Searching Strategies
The app has 7 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.