0
Write an algorithm for binary search.
program on binary search • 3.6k  views
0
0

Binary search algorithm works on the principle of divide and conquer. This algorithm works with the sorted data. Binary search looks for an element to be searched in the middle first, if the element matches with the required one then it is returned as an output otherwise the whole list is considered into two parts i.e left side list and right side list.

If the element to be searched is greater than an element in the middle position then required element is searched into left side of the array otherwise element is searched on the left side of the array. This process is carried on until element from an array matches the required element.

// algorithm for binary search

BINARY_SEARCH(A, lower_bound, upper_bound, VAL)

Step 1: [INITIALIZE] SET BEG = lower_bound
END = upper_bound, POS = - 1
Step 2: Repeat Steps 3 and 4 while BEG <= END
Step 3: SET MID = (BEG + END)/2
Step 4: IF A[MID] = VAL
SET POS = MID
PRINT POS
Go to Step 6
ELSE IF A[MID] > VAL
SET END = MID - 1
ELSE
SET BEG = MID + 1
[END OF IF]
[END OF LOOP]
Step 5: IF POS = -1
PRINT “VALUE IS NOT PRESENT IN THE ARRAY”
[END OF IF]
Step 6: EXIT

0