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).

Algorithms using Python : #2 Binary Search
binary search algorithm
  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 
            return binarySearch(arr, mid+1, r, x) 
        # 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.

Please feel free to add-on or point out correction on my post in the comments section.


Please enter your comment!
Please enter your name here