predictivesearch ~stable

A searching algorithm which may be faster than binary search


To use this package, run the following command in your project's root directory:

Manual usage
Put the following dependency into your project's dependences section:

PredictiveSearch

A searching algorithm which may be faster than binary search

(this depends on your architecture, as it reduces array accesses in exchange for extra branches)

If you've ever been told that binary search is theoretically optimal: this would be the counter-proof.

Both algorithms work on average in O(log(n)) time, but this one is more likely to get the value on the first (or rather third) try.

It works on the requirement that the data is sorted and on the assumption that it is uniformally distributed. This should still be comparable to or better than binary search for most arrays, as even if it isn't uniformally distributed, if it is random, then subarrays will increasingly be closer to a uniform distribution as their size decreases.

Of course, it is possible to generate an array where this devolves into linear search but in general, it shouldn't happen.

Authors:
  • phebert5009
Dependencies:
none
Versions:
1.0.2 2024-Feb-12
1.0.1 2024-Feb-12
1.0.0 2024-Feb-12
~stable 2024-Feb-12
Show all 4 versions
Download Stats:
  • 0 downloads today

  • 0 downloads this week

  • 0 downloads this month

  • 1 downloads total

Score:
0.3
Short URL:
predictivesearch.dub.pm