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