While solving the problem on Leetcode https://leetcode.com/problems/find-median-from-data-stream I came across an insertion sort approach. However, the pop quiz mentions using linear search instead of binary search. I wonder why is that, and what are the trade-offs?
2 Answers
My guess is if you are searching for number i, instead of searching from the beginning, you can start searching from the index i. But this only works well if the numbers do not contain a lot of duplicates.
The problem will cost O(n) both in linear search and binary search, so just do the easier linear search.
Related