Binary Search

One of the most interesting algorithms of research is binary search algorithm.
This is the fastest algorithm (algorithm of binary trees apart) to search a data inside a group of
elements. In fact it runs in a worst log2(x) comparisions before to find (or not) the data.
The only prerequisite is : the set of elements where to search the data must be sorted.
Below an example of this algorithm.
int binary_search( int arr[], int tot_el, int data )
{
/* Declaration and initialization of variables */
int el = 0;
int me = 0;
int count = 0;
/* Start program */
el = tot_el-1;
while (count <= el) { /* me is the element in the middle of array */ me=(count+el) /2; /* data found!! return the array index*/ if (arr[me] == data) return me; if (arr[me] > data)
el = me-1
else
count = me +1
}
/* If I found nothing -1 return */
return -1;
}
/* End program */
where the parameters are :
arr = Array the contains the elements where to search the data that we need
tot_el = Number of elements inside arr
data = element to find
For each iteration the algorithm gets the middle element of array.
If it’s equals to data the program ending and return the index of array where the data is present.
if the data is greater then element in the middle of array, the algorithm evaluate the second part of
the array (from middle to end) discarding the first part, otherwise if the data is lesser then element
in the middle of array the algorithm evaluate the first part of the array (from begin to middle)
discarding the second part.
At the end the process returns index of the array if the data has been found, -1 if not.

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *