A binary search or half-interval search algorithm finds the position of a target value within a sorted array.
Step#1 Find the mid_element of array and compare it to target_value.
Step#2 If target_value == mid_element,
If target_value < mid_element,
then the search continues on the lower half of the array;
If target_value > mid_element,
then the search continues on the upper half of the array.
Step#3 Repeat the Step#2 (eliminating half of the elements) until the target value is either found, or until the entire array has been searched.
Worst case performance O(log n)
Best case performance O(1)
Average case performance O(log n)
Worst case space complexity O(1)