When working with a very large list of items, you might want to use a weighted search. One where instead of jumping to the middle, you try to get closer to your choice.
Consider you had list with values between 1 and 10,000,000, and you were looking for an item with a value of 8,536,324. Jumping to the middle and discarding half of the possible items is one way, however with 10,000,000 items, it will still take some time.
What if we could discard 80% of them, instead of just 50%? That’s the idea behind a weighted jump. Now sometimes we’ll get on the wrong side and only discard 20%. That’s the risk, however, given the law of averages, we should be no worse than the binary search, and possibly better.
It works by finding out the elements at our high and low index, and then moving to an index closer to the two based upon what you are searching for.
Consider the following, using the values of being between 1 and 10,000,000 like in our example before.
searchIndex = int(searchValue / array[high] * high ))
This gives us a starting index of around the 85% mark. Working this through a few times, and we get close to the actual number.
However, because you can be on the wrong side of your guess, most people stick with the binary search.
Weighted Search was originally found on Access 2 Learn
