Binary search is one of the fundamental algorithms in computer science. It relies on a divide and conquer strategy to find a value within an already-sorted collection. For binary search, the array should be arranged in ascending or descending order. In each step, the algorithm compares the search key value with the key value of the middle element of the array. If the keys match, then a matching element has been found and its index, or position, is returned. Otherwise, if the search key is less than the middle element's key, then the algorithm repeats its action on the sub-array to the left of the middle element or, if the search key is greater, on the sub-array to the right. If the remaining array to be searched is empty, then the key cannot be found in the array and a special "not found" indication is returned. log2(N)-1 is the expected number of problems in an average successful search, and the worst case is log2(N). If the list is empty, no problems at all are made. Thus binary search is a logarithmic algorithm and executes in O(log N) time. In most cases it is considerably faster than a linear search. It can be implemented using iteration, or recursion.
