Tuesday, September 2, 2008

BINARY SEARCH ALGORITHM

BINARY SEARCH ALGORITHM

The binary search algorithm is used to find out whether an element 'x' is present in a set of data which is in ascending order.


Consider a numeric array of size '
which is sorted in ascending order. We have to search for an element 'x´in this array.


Elements of this array can be written as A(1), A(2), A(3), … A(n). First find the middle value in the array, as follows:

If the array contains even number of elements, then:


Middle element = (n + 1) DIV 2

Compare the value of x with this middle element.

If the value of x is greater than the value of the middle element, adjust the lower limit like this:

Lower = middle + 1

Calculate middle element:

Middle = (lower + upper) DIV 2

If the value of x is less than the value of the middle element, adjust the lower limit like this:

Upper = middle - 1

Thus, each time one half of the array is not searched.

Algorithm:

1. Establish the sorted array of size n and element to be found x.

2. Set upper and lower limits.

3. Repeatedly:

a) Calculate the middle position of the array.

b) If value to be found (x), is greater than middle value, then

Adjust lower limit as:

Lower = middle + 1

Else adjust upper limit as:

Upper = middle - 1

Until sought value is found or lower > upper.

----------------------------------------------------------------------------------------------------------------

Post a Comment