Binary Search Algorithm

• This works efficiently on a sorted list.
• Hence, in order to search an element in a list using the binary search technique, that list should be sorted.

The list is divided into two and the given item is compared with the middle element of the list. If the match is found then, the location of the middle element is returned otherwise, we search into either of the halves depending upon the result produced. See the steps below.

Steps:-

• VAL is the value entered by the user.
• 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

As we have learned the Binary Search Algorithm today, try out these four questions.😃

http://www.quiz-maker.com/QD9LE85