Binary search algorithm:
A binary search algorithm is the most common type of searching algorithm
that is still widely used in system programming and another software
programming, binary search algorithm is an upgraded version of a linear
search algorithm.
How is binary search faster than linear search?
Binary search Algorithm used the divide and concur technique to find the "ITEM". It divides the whole sorted list into two parts through the help of ITEM that is presented into the 'MIDDLE' of the list. The complexity of the Binary Search Algorithm is [ O(log2n) ] that is less time-consuming and more efficient than the Linear Search Algorithm Complexity is [ O(n) ].
Binary search Algorithm:
DATA is refer to list of N sorted array. // DATA=[2, 3, 4, 5,...,
N]
Step 1. { Initialize variables }
SET BEGINNING = LOWER-BOUND
SET ENDING = UPPER BOUND
SET MIDDLE = INT (( BEGINNING+ENDING) / 2)
Step 2. Repeat Steps 3 & 4 WHILE "BEGINNING<=ENDING" and DATA[MIDDLE] != SEARCH_ITEM.
Step 3. IF ITEM < DATA[MIDDLE] , then:
Set ENDING = MIDDLE+1.
ELSE :
Set BEGINNING= MIDDLE+1. // now if statement is closed.
Step 4. SET MIDDLE= INT (( BEGINNING+ENDING) / 2).
Step 5. IF DATA [MIDDLE] = ITEM, then:
Set LOCATION = MIDDLE.
ELSE:
Set LOCATION = NULL.
Step 6. FINISH
Examination question of Binary Search Algorithm :
Q1. Explain Binary Search Algorithm and its advantages with example.
Binary Search is an optimistic technique when working on sorted data items. binary search reduce the time and space complexity through filtering the data in each iteration. It jump over the list after comparing the searching item with the middle location and then take the accurate decision to moves left or right side of the list .
Example 1 :
[ ALGORITHM ]
DATA = [100,200,300,400,500,600,700]
Search_Item = 500
Step 1. Initially, Beg =1 , End= 7.
MID= Beg+End / 2 = 8/2 = 4, then:
DATA[MID]=400
Step 2. Now, 500>400, BEG becomes change by BEG=MID+1=5, End =7.
MID= BEG+END/2= 12/2= 6, then :
DATA[MID]=600
Step 3. 500< 600,
So then, END becomes changes with,
END = MID-1 =5, BEG= 5
MID= BEG+END/ 2 = 5, then :
DATA[MID] =500
Hence, We found Search_Item in location= 5.
Example 2 :
DATA = [100,200,300,400,500,600,700]
Search_Item = 550
1. Initially, Beg =1 , End= 7.
MID= Beg+End / 2 = 8/2 = 4, then:
DATA[MID]=400
2. Now, 500>400, BEG becomes change by BEG=MID+1=5, End =7.
MID= BEG+END/2= 12/2= 6, then :
DATA[MID]=600
3. 550< 600,
So then, END becomes changes with,
END = MID-1 =5, BEG= 5
MID= BEG+END/ 2 = 5, then :
DATA[MID] =500
Hence, We did not found Search_Item=550 in location= 5.
