`closest` does too many comparisons

[rocketraman]

I haven't closely examined the reason why, but in some very basic testing, there were more comparisons than there should have been for an efficient binary search of the closest value. For example, the search:

bs.closest([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 4, function(value, find) {
  console.log(`Comparing value ${value} with target ${find}`)
  if(value > find) return 1
  else if(value < find) return -1
  return 0
}) 

outputs:

Comparing value 4 with target 4
Comparing value 2 with target 4
Comparing value 3 with target 4
Comparing value 4 with target 4

One option that probably should be supported is to tell the search algorithm that there are no duplicated values so there is no extra work to find the first matching value. That would reduce the comparison count to 1 in the above search.

But even accounting for possible duplicates, there is still an extra comparison.

[soldair]

thanks for the find. ill take a look

[soldair]

if it finds a matching value it should just return even if the array has duplicates

[rocketraman]

if it finds a matching value it should just return even if the array has duplicates

Well, I can see what it wouldn't -- because in your README you say closest returns the first matching value, so it has to continue to verify that it has indeed found the first one. This is why I suggested being able to specify in the options that there are no duplicates -- then you can shortcut the extra comparisons.

[soldair]

you're right. hopefully I can look tonight its kinda the whole point of this lib :) On Jun 23, 2015 1:08 PM, "Raman Gupta" [email protected] wrote:

if it finds a matching value it should just return even if the array has duplicates

Well, I can see what it wouldn't -- because in your README you say closest returns the first matching value, so it has to continue to verify that it has indeed found the first one. This is why I suggested being able to specify in the options that there are no duplicates -- then you can shortcut the extra comparisons.

— Reply to this email directly or view it on GitHub https://github.com/soldair/node-binarysearch/issues/4#issuecomment-114625958 .