Binary Search Algorithm

Description

The binary search algorithm is a divide and conquer algorithm, that takes a sorted array as an input. It works by comparing the searched value (key) to the middle element of the array. If they match, then its index is returned. If the key is less than the middle element, the algorithm is invoked on the left sub-array, otherwise it is invoked on right sub-array. This continues until the key is found or the input array is reduced to zero.

Recursion tree

Recursion tree

(more…)