Advertisement Remove all ads

Write an Algorithm for Binary Search Method. Explain Algorithm with Suitable Example. - Computer Science 1

Answer in Brief
Short Note

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

Advertisement Remove all ads

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

Concept: Basic Data Structures (Stack, Queue, Dequeue)
  Is there an error in this question or solution?
Advertisement Remove all ads

APPEARS IN

Advertisement Remove all ads
Advertisement Remove all ads
Share
Notifications

View all notifications


      Forgot password?
View in app×