Question

 Explain Binary Scarch algorithm with a suitable example.

Answer 1

1) Binary search is used to search an element from sorted array. 2) Algorithm for Binary Search : (Binary Search) BINARY [DATA, LB, UB, ITEM, LOC] Here DATA is sorted array with lower bound LB and upper bound UB and ITEM is given item of information. The variables BEG, END and MID denote respectively the beginning, end and middle location of a segment of elements of DATA. This algorithm finds the location LOC of ITEM in DATA or set LOC=NULL. 
1. [Initialize segment variables.]
Set BEG: = LB, END: = UB and MID=INT [(BEG+END)/2]
2. Repeat steps 3 and 4 while BEG <= END and DATA [MID]  ITEM
3. IF ITEM < DATA [MID], then:
Set END: = MID-1    
Else:
Set BEG: = MID+1
[End of IF structure]
Set MID: =INT [(BEG+END)/2]
[End of step 2 loop]
IF data [MID] = ITEM, then:
Set LOC: =MID
Else:
Set LOC: =NULL
[End of IF structure]
4. Exit.
3) Example: Suppose array given is,
10, 20, 22, 24, 26
if you want to check whether 24 is present or not.
a) find mid → LB = 1 , UB = 5

mid = INT `(("UB" +"LB")/2) = "INT" ((1+5)/2)`

mid = 3 → mean 22

b) if item < mid 

end = mid -1

else
 beg = mid + 1 
24 > 22 
beg = mid  + 1 = 3 + 1 = 4 →  means26

c) beg = 4, end = 5 =`INT((4+5)/2) = 2`  
 mid =24 ,which is our search element; its position is = 4.