BINARY SEARCH (MCA Related Topic) this is not BINARY SEARCH TREE

BINARY SEARCH (MCA Related Topic) this is  not BINARY SEARCH TREE

 

Binary Search algorithm searches a given value or element in an already sorted array
by repeatedly dividing the search interval in half. It first compares the value to be
searched with the item in the middle of the array. If there is a match, then search is
successful and we can return the required result immediately.
 But if the value does not match with the item in middle of the array, then it finds whether the given value is less than or greater than the value in the middle of array. If the given value is less than the
middle value, then the value of the item sought must lie in the lower half of the array.
However, if the given value is greater than the item sought, must lie in the upper half
of the array.
 So we repeat the procedure on the lower or upper half of the array
according as the given value is respectively less than or greater than the middle value.
The following C++ function gives the Binary Search Algorithm.

Explanation of the Binary Search Algorithm
It takes as parameter the array A, in which the value is to be searched. It also takes
the lower and upper bounds of the array as parameters viz., low and high respectively.
At each step of the interation of the while loop, the algorithm reduces the number of
elements of the array to be searched by half. If the value is found then its index is
returned. However, if the value is not found by the algorithm, then the loop terminates
if the value of the low exceeds the value of high, there will be no more items to be
searched and hence the function returns a negative value to indicate that item is not
found.

int Binary Seach (int * A, int low, int high, int value)
{ int mid:
       while (low < high)
         { mid = (low + high) / 2;
                if (value = = A [mid])
                      return mid;
               else if (value < A [mid])
                          high = mid – 1;
                        else low = mid + 1;
         }
    return ─ 1;
}

Analysis
As mentioned earlier, each step of the algorithm divides the block of items being
searched in half. The presence or absence of an item in an array of n elements, can be
established in at most lg n steps.

Thus the running time of a binary search is proportional to lg n and we say this is a O(lg n) algorithm.