Advertisement Remove all ads

Explain Binary Scarch Algorithm with a Suitable Example. - Computer Science 1

Answer in Brief

 Explain Binary Scarch algorithm with a suitable example.

Advertisement Remove all ads

Solution

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.

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×