Question

Write an algorithm for Binary Search Method. Explain algorithm with suitable example.

Answer 1

Binary search is used to search an element from sorted array. 
Algorithm : Binary search
Binary (DATA, LB, UB, ITEM, LOC)
Here DATA is a sorted array with lower bound LB and upper bound UB. ITEM is given element. BEG
denotes beginning, MID denotes middle and END denotes end location of DATA. This algorithm finds the
location LOC of ITEM in DATA or sets LOC = NULL, if search is unsuccessful.
Step 1: [Initialize Variables]
Set BEG = LB, END = UB and MID = INT (BEG + END)/2)
Step 2: Repeat steps 3 and 4
while BEG = END AND DATA (MID)  ITEM
Setp 3: If ITEM < DATA [MID], then :
set END = MID - 1
Else :
Set BEG = MID + 1
[End of If structure]
Step4 : Set MID = INT (BEG + END)/2)
[End of step 2 loop]
Step5 : If DATA [MID] = ITEM, then :
set LOC = MID
Else :
LOC = NULL
[End of If structure]
Step6 : Exit
e.g. Given DATA be the following sorted 13 element array : 
11 22 30 33 40 44 55
60 66 77 80 88 99
Suppose ITEM = 40
Step1: Intially BEG = 1 and END = 13
Hence MID = INT [(1 + 13)/2] = 7
and so DATA [MID] = DATA [7] = 55
Step2 : Since 40 < 55, END has its value changed by
END = MID - 1 = 7 - 1 = 6
Hence MID = INT [(1 + 6)/2] = 3
and so DATA [MID] = DATA [3] = 30
Step3 : Since 40 > 30, BEG has its value changed by
BEG = MID + 1 = 3 + 1 = 4
Hence MID = INT [(4 + 6)2/] = 5
and so DATA [MID] = DATA [5] = 40
∴ found ITEM in location LOC = MID = 5