Binary Search in Data Structure

Binary Search in Data Structure

Binary search the array is divided into two equal part. The element is compared
with middle element. If it is smaller, it is searched in first half, but if the middle is
bigger, it is searched in second half. This is repeated and in next stage we have
to search only in one quarter of list and so on.

Advantage

In binary search method, searching is faster as comparison to linear search.

Disadvantage

Binary search method is applicable only on sorted list


Algorithm

Binary search (A, LB, UB, DATA, LOC)
Step 1
Set FIRST = LB
Set LAST = UB
MID = INT[FIRST + LAST]/2
Step 2.
Repeat step 3 and 4 while
LAST >= FIRST and A[MID] =/ DATA
Step 3
If DATA < A[MID] then Set LAST = MID-1 Else Set FIRST = MID +1 Step 4
Set MID = INT[FIRST+LAST]/2
Step 5
If A[MID] = DATA then
Set LOC = MID
else
Set LOC = NULL
Step 6
EXIT