Question

Write an algorithm for the binary search method. Explain algorithm with a suitable example.

Write the binary search algorithm with a suitable example.

Define the following.

Write down the method or algorithm to find out an element using binary search with an example.

Answer 1

Algorithm: Binary Search
Binary(DATA, LB, UB, ITEM, LOC)
Step 1: Initialize
        BEG = LB
        END = UB
        MID = INT((BEG + END) / 2)
Step 2: While BEG ≤ END AND DATA[MID] ≠ ITEM
            If ITEM < DATA[MID] then
                END = MID - 1
            Else
                BEG = MID + 1
            End If
            MID = INT((BEG + END) / 2)
        End While
Step 3: If DATA[MID] = ITEM then
            LOC = MID
        Else
            LOC = NULL
        End If
Step 4: Exit

Example:

Given a sorted array:

11 22 30 33 40 44 55 60 66 77 80 88 99

ITEM = 40

LB = 1, UB = 13

BEG = 1, END = 13
MID = INT((1+13)/2) = 7 → DATA[7] = 55

40 < 55 → END = 6
MID = INT((1+6)/2) = 3 → DATA[3] = 30

40 > 30 → BEG = 4
MID = INT((4+6)/2) = 5 → DATA[5] = 40

ITEM found at location 5.