Remix.run Logo
zkmon 6 hours ago

Some algorithms such as binary search give an incorrect view of the overall cost. The search has a prerequisite of sorting. So, the assumption is, the data is sorted once, and searched several times, making the sorting cost insignificant.

What if the data is used for only a single lookup? For this case, actually a sequential search would have lower cost compared to sorting and binary search. Infact, sequential search may beat sorting and binary search for upto about 100 lookups. So I think it is important to consider overall cost.

auggierose 3 hours ago | parent | next [-]

It is not an "incorrect view of the overall cost".

Binary search talks about how long the search takes with this particular algorithm assuming the data is sorted. It does not talk at all about scenarios where the data is not sorted. In particular, it does not provide any views on costs without this assumption, let alone an incorrect one.

Yes, YOU need to consider when it is appropriate to use binary search. That is the case with all algorithms you will ever apply, and goes without saying.

fiddlerwoaroof 6 hours ago | parent | prev [-]

But how the data got sorted is irrelevant to the speed of the algorithm: for example, you could use binary search as part of an algorithm to find the insertion point of a new element in an always sorted data structure, meaning that sorting the data is never necessary.

zkmon 5 hours ago | parent [-]

The overall journey matters. For example, for some flight journeys, the flight-time is only a fraction of the overall time taken by the journey, which could makes it faster if you use road or rail transport. Flight speed doesn't matter.