A binary search or half-interval search algorithm finds the position of a target value within a sorted array. The binary search algorithm can be classified as a dichotomies divide-and-conquer search algorithm and executes in logarithmic time.

The idea of binary search is to use the information that the array is sorted and reduce the time complexity to O(Log n).

1. Compare x with the middle element.
2. If x matches with middle element, we return the mid index.
3. Else If x is greater than the mid element, then x can only lie in right half subarray after the mid element. So we recur for right half.
4. Else (x is smaller) recur for the left half.
``````# Returns index of x in arr if present, else -1
def binarySearch (arr, l, r, x):

# Check base case
if r >= l:

mid = l + (r - l)/2

# If element is present at the middle itself
if arr[mid] == x:
return mid

# If element is smaller than mid, then it can only
# be present in left subarray
elif arr[mid] > x:
return binarySearch(arr, l, mid-1, x)

# Else the element can only be present in right subarray
else:
return binarySearch(arr, mid+1, r, x)

else:
# Element is not present in the array
return -1``````

Program Explanation

1. The user is prompted to enter a list of numbers.
2. The user is then asked to enter a key to search for.
3. The list and key is passed to binary_search.
4. If the return value is -1, the key is not found and a message is displayed, otherwise the index of the found item is displayed.