Probabilistic Binary Search Algorithm
This paper is intended for people who are already acquainted with the Binary Search algorithm which finds the position of a “Target” value within a sorted array by repeatedly splitting the list of remaining candidates into two parts and ruling out one part, until the Target value is found.
Traditional binary search is fine when there is certainty of which half of the remaining candidates to eliminate at each iteration. However, there are real World situations when the information about which is the correct half can be false or even non-existent. In these situations, a probabilistic approach is suggested especially if checking for the Target value is very “expensive”. Below I describe a simplified version of an algorithm I have developed for such a situation.
The main idea is to assign a probability to each element in the array to be searched and prioritise parts of the array with higher probabilities. We begin with the assumption that each element has equal probability of being the target, hence 1/n if there are n elements. We adjust these probabilities after each iteration of checking.
We loop for a maximum of n times (worst case scenario is that all information is false or non-existent and that we are very unlucky). At each iteration, we check if the element is the Target. If so, then we have the answer and can exit. If not, then we check for a “directional clue”: is the Target further up or down the array. In a conventional binary search, the directional clue is always correct, however in probabilistic search, there is a possibility that the clue is sometime false. Assuming that the probability that the directional clues are correct is known, then we can adjust all the probabilities of the elements accordingly. If the accuracy rate of the directional clues is not known then we can make an assumption such as 80% or 90%.
An Example
Let’s assume the following challenge: we have a deck of 10 cards. One random card has the word “Target” written on it. The 10 cards are laid out in a row. We have no idea which card is the target card. Cards to the left of the Target card, in principle, have the words “Target is to the right”, and cards right of the Target, in principle, have the words “Target is to the left. We will call these left and right cards: “information cards”. Now, the person whose job it was to mark the information cards is a bit incompetent and tends to get the marking wrong 20% of the time, ie the accuracy rate is 80%. The cards are all face down and appear identical so we initially have no idea what is inscribed on each card.
The goal is to find the target card by flipping as few cards as possible.
Despite the accuracy rate being below 100%, the information cards will still useful to help us find the Target card quicker than if there was no information.
The approach
Before starting, we can assume that each card has a probability of 10% of being the Target card. We then start by checking card number 5 (a mid-point is a good place to start) which says “Target is to the Left”. We can now re-evaluate all the probabilities the cards:
- Cards 1 to 4 now each have a probability of 19.05% of being the Target.
- Card 5 now has 0 probability.
- Cards 6 to 10 now each have a probability of 4.76% of being the Target
(Note that the calculation of the probabilities is not straightforward. The conditional probability formula was used: Probability(Target is to the left) / Probability(card5 says Target to the left) =
(5/9 x 20%) / (4/9 x 80% + 5/9 x 20%), and then divide this number by 4 as there are 4 cards to the left of Card 5. Although this may seem complicated, a major simplification can be used in the algorithm which is discussed further below.)
We then draw card number 2. The card says: “Target is to the right”. The probabilities are now:
- Card 1 has probability 7.41%
- Card 2 has probability 0
- Cards 3 and 4 each have probability 28.57%
- Card 5 has probability 0
- Cards 6 to 10 now each have a probability 7.14%
The common sense strategy would be to now pick either card 3 or 4 as they have the highest probabilities. In fact card 4 is a better choice, because it is closer to the “centre of gravity” of the aggregate probabilities.
Now let’s assume that we flip card 4 and it says that “Target is to the right”. This is in contradiction to card 5 we flipped at the beginning which said “Target is to the left”. One of the cards must therefore be wrong. In a normal binary search we would be stuck, but in a probabilistic search, we just plough on by re-calculating the probabilities, which become:
- Card 1 has probability 4%
- Card 2 has probability 0
- Card 3 has probability 16%
- Card 4 has probability 0
- Card 5 has probability 0
- Cards 6 to 10 now each have a probability 16%
The above probabilities are not surprising as card 1 has had 1 clue out of 3 in it’s favour, whereas the other remaining cards have had 2 clues out of 3 in their favour which is why they all have equal probabilities.
The idea is to repeat the iterations and each time select a card which roughly splits the sum of the probabilities 50/50 either side until we reach the Target. Binary search is similar to this approach but represents a unique case where the directional information is 100% accurate.
A Simplification
Instead of calculating exact probabilities in the purist fashion where the sum of probabilities is equal to 1, we can use probability weights instead, whereby a weighting of 10 has five times the probability of a weighting of 2. This saves us from having to calculate the denominator component of the probability fractions and as a result makes the code easier to write and faster to execute.
We start off by assigning every element in the array with a probability weight of 1, and each time we discover a clue we multiply the weights of all the elements that are validated by the clue by the “information factor”. In the example above the “information factor” would be 5 which is the inverse of 1–80%, where 80% was the accuracy rate of the clues. If the accuracy rate of the information is unknown, then I suggest a factor of 5.
At each iteration the best guess is the element closest to the centre of gravity of the probability distribution curve, or to put it another way, the first element in the array where the sum of all the probability weights of it and the preceding elements is 50% or more of the total.
We have the added complexity that sometimes when doing a check there is no clue information. In this event, we simply leave the probability weights unchanged, except for the element that has been checked whose weight gets reduced to zero.
In pseudocode, this is how the code could look:
# T = target element we are looking to find
# A = Array of n elements where we seek the find the object A[t] = T
# Elements in array A that are not equal to T have a clue indicating relative
# position of A[t]. Clues are:
# • L: somewhere to the left in the array
# • R: somewhere to the right in the array
# • 0: no information
# f = is the “information factor”, ie 1/(1-information accuracy rate). If unknown then
# assume 80% (selecting the optimal value is a subject for another paper!).
PSEUDOCODE
— — — — — — — — — -
function probabilistic_binary_search (A, n, T, p)
# we start off by assigning equal probabilities for all elements
array P[m] = 1, for m = 0 to n -1
#Define f as the probability multiplier we will use for adjusting probabilities
f = 5 # this is equivalent to information accuracy rate of 80%
# Define i as the search index. A good starting point is the midpoint
i = int(n/2)
# Loop for a maximum of n objects
For x = 1 to n
if A[i] = T then return i # We have found the Target so return the index
if A[i] = L then P[m] = P[m] * f, for m = 0 to i-1
if A[i] = R then P[m] = P[m] * f, for m = i+1 to n-1
P[i] =0 # this is not the Target so we give it zero probability
# Note we simply ignore the case A[i] = 0
# Set the search index to the most probable location, ie the mid point of the
# probability distribution curve
i = get_mid_point(P)
next x
end
- — — — — — -
- — — — — — -
function get_mid_point (array P)
#calculate sum of probability weights
Psum = 0
for j= 0 to length(P) -1
Psum = sum + P(y)
next j
#find midpoint
sum = 0
for y = 0 to length(P) -1
sum = sum + P(y)
if sum >= Psum/2 then return y
next y
return y
Enhancements
The above code purposefully over-simplified for the sake of ease of understanding. Many enhancements can be made such as:
- The code for finding the midpoint can be improved by updating Psum when the individual probabilities are updated
- If n is very large, a separate mapping array can be used to summarise the probabilities
- The above code assumed a constant accuracy rate. This may in fact vary for each clue
- We have also assumed only 2 types of clue: “to the left” and “to the right”. There could be many more types such as “near left”, “far left”, “odd index” etc.
- We could be searching in a multi-dimensional space
