Re: Re: Potential binary search optimization or feature

Am 14.04.2015 20:24 schrieb "Danylo Medinsky" <medinsky94@gmail.com>: > > ... until I can determine how much performance will be compromised > from the sorting. Sorting at least has to look at each array element once, and execute the comparison function once. Compare that to a searching scan, which can terminate once it finds the element it is looking for. You would need to remember that the array is already sorted, and make several binary searches (more than log(count(array)), to get a win. But with an arbitrary comparison function you cannot remember whether the array is sorted, because it is only sorted wrt. that specific comparison function. The only scenario where sort-first-then-search can make sense, is when you have to search for several items "in parallel" under a given comparison function, and your number of items to search for is clearly larger than log(count(array)). Patrick