7 ms·
Linear search if it's not sorted. If it's sorted binary search will be much faster. So you need a flag for the function to tell it to use one of the two. This i
by chinmaythosar 6y ago
Linear search if it's not sorted. If it's sorted binary search will be much faster. So you need a flag for the function to tell it to use one of the two. This is why writing generic functions can be tricky. Programmers may use something inefficient just because it makes their lives easier.
- harikb 6y agoDoes Ruby track that a list is already sorted? If not, you are still adding cognitive overhead for the programmer to track it
- vinger 6y agoYou can sort by many things. Knowing where you sort (usually as far up the chain as possible) is important
- z0r 6y agolinear search can be faster than binary search for small arrays, depending on your processor architecture. writing generic functions is difficult, so it's nice if a language allows people to do so, otherwise you get N inefficient and/or buggy reimplementations of the function in every project needing it. (not sure if that is your point)
- chinmaythosar 6y agomy point was that the author uses an example like search and called go not an easy language. so i was trying to give an example where it's not necessary a linear search or search is trivial ...
- anonymoushn 6y agoIf your developers hand write a binary search to delete an element you are extremely likely to end up with bugs. So it would be nice if there was a generic binary search too.
- BenFrantzDale 6y agoThat Go doesn’t have the equivalent of `std::lower_bound` is pretty ridiculous.
- arp242 6y agoLinear search is also quite a bit faster than maps for small arrays (in Go at least, last time I tested it).
- hderms 6y agoobligatory link: https://www.evanjones.ca/linear-search.html https://www.evanjones.ca/linear-search.html
- jtsiskin 6y agoBinary search won’t be any faster (in big O) because it’s backed by an array: you’ll still need to copy every element after the removed one from slot n to n-1.