Question

Explain Binary Scarch algorithm with a suitable example.

Explain binary search algorithm.

Answer 1

Binary search is a technique used to locate an element in a sorted array.

Algorithm: Binary Search

Binary (DATA, LB, UB, ITEM, LOC)

In this algorithm, DATA represents a sorted array with LB as the lower bound and UB as the upper bound. ITEM is the element to be searched. BEG indicates the beginning, MID represents the middle position, and END denotes the ending position of DATA. The algorithm determines the position LOC of ITEM in DATA, or assigns LOC = NULL if the search is unsuccessful.

Step 1: [Initialize Variables]
             Set BEG : = LB, END := UB and MD := INT ((BEG +                         END)/2)

Step 2: Repeat steps 3 and 4
             while BEG = END AND DATA[MID] ITEM

Step 3: If ITEM < DATA[MID], then :
             set END := MID − 1
             Else :
             Set BEG := MID + 1
             [End of If structure]

Step 4: Set MID := INT ((BEG + END)/2)
             [End of step 2 loop]

Step 5: If DATA[MID] = ITEM, then :
             set LOC := MID
             Else :
             LOC := NULL
             [End of If structure]

Step 6: 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

Step 1: Initially BEG = 1 and END = 13
             Hence MID = INT[(1 + 13)/2] = 7
             and so DATA[MID] = DATA [7] = 55

Step 2: 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

Step 3: 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