Implementation of Binary Search

Binary Search implementation

There can be two ways to implement Binary Search: recursive and iterative.

We will look at the recursive approach first. In this, we basically ignore half of the elements after just one comparison.

• Compare the key with the middle element.
• If the key matches with the middle element, return the mid index.
• Else if the key is greater than the mid element, then the key can only lie in the right half sub-array after the mid element. So we recur for the right half.
• Else (key is smaller) recur for the left half.

Look at the code below: