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

#### Solution

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