ALGORITHM FOR BINARY SEARCH

ALGORITHM FOR BINARY SEARCH IN AN ARRAY:

In Binary searching,firstly the array is divided into two halves then the element to be searched for is searched in the first half if the element is lesser than the middle element of the array. Otherwise second half is searched for the element.This binary division is continued to the half in which searching is being done and until we find the element. If element is found then algorithm returns a true value otherwise  it returns a false value.
NOTE: For binary searching the array should be sorted in an order.

BINARY(A,LB,UB,ITEM,LOC): Here A is an sorted array with lower bound LB and upper bound UB and ITEM is a given item of information. The variables BEG, END and MID denote, respectively, the beginning,end and middle locations of a segment of DATA. This algorithm finds the location LOC of ITEM in DATA or sets LOC=NULL.

1. Set BEG=LB,END=UB and MID=INT((BEG+END)/2)
2. Repeat Steps 3 and 4 while BEG<=END and
                  A[MID]!= ITEM
3. If ITEM < A[MID]  then
             Set END= MID-1
    Else
              Set BEG= MID+1
  [End of If structure]
4. Set MID = INT((BEG+END)/2)
      [End of Step 2 loop]
5.If A[MID]=ITEM then
        Set LOC=MID
   Else
        Set LOC=NULL
[End of If structure]
6. Exit.