Probability search in data structure and algorithm?

Answer 1

manu_del In Probability Search , the list is ordered with most probable search element at the beginning of the list and least probable at the end.

Useful when a relatively small number of elements are the targets for most of the searches. To ensure that the probability ordering is correct over time, in each search we exchange the located element with the element immediately before it in the list.

This is a sample ProbabilitySearch program for a list of integers

INPUT:

list[] : reference of integer array

last : index of last item

target: target to be found

ref_locn: reference to the location of target

OUT:

If target is found

location of target is stored in ref_locn

found = 1 is returned

target is moved up in priority

Else

last is stored in ref_locn

found = 0 is returned

int ProbabilitySearch (int list[],int last, int target, int *ref_locn)

{

int looker = 1;

int found = 0;

int temp;

while(looker <= last && target != list[looker])

{

looker = looker + 1;

}

if(target == list[looker])

{

found = 1;

if(looker > 1)

{

temp = list[looker -1];

list[looker -1] = list[looker];

list[looker] = temp;

looker = looker -1;

}

}

else

found = 0;

*ref_locn = looker;

return found;

}