What is recursive binary search in python?

View Discussion

Improve Article

Save Article

  • Read
  • Discuss
  • View Discussion

    Improve Article

    Save Article

    In a nutshell, this search algorithm takes advantage of a collection of elements that is already sorted by ignoring half of the elements after just one comparison. 

    1. Compare x with the middle element.
    2. If x matches with the middle element, we return the mid index.
    3. Else if x is greater than the mid element, then x can only lie in the right (greater) half subarray after the mid element. Then we apply the algorithm again for the right half.
    4. Else if x is smaller, the target x must lie in the left (lower) half. So we apply the algorithm for the left half.

    Recursive :

    Python3

    def binary_search(arr, low, high, x):

        if high >= low:

            mid = (high + low) // 2

            if arr[mid] == x:

                return mid

            elif arr[mid] > x:

                return binary_search(arr, low, mid - 1, x)

            else:

                return binary_search(arr, mid + 1, high, x)

        else:

            return -1

    arr = [ 2, 3, 4, 10, 40 ]

    x = 10

    result = binary_search(arr, 0, len(arr)-1, x)

    if result != -1:

        print("Element is present at index", str(result))

    else:

        print("Element is not present in array")

    Output:  

    Element is present at index 3

    Time Complexity: O(log n)

    Auxiliary Space: O(logn)     [NOTE: Recursion creates Call Stack]

    Iterative:
     

    Python3

    def binary_search(arr, x):

        low = 0

        high = len(arr) - 1

        mid = 0

        while low <= high:

            mid = (high + low) // 2

            if arr[mid] < x:

                low = mid + 1

            elif arr[mid] > x:

                high = mid - 1

            else:

                return mid

        return -1

    arr = [ 2, 3, 4, 10, 40 ]

    x = 10

    result = binary_search(arr, x)

    if result != -1:

        print("Element is present at index", str(result))

    else:

        print("Element is not present in array")

    Output:  

    Element is present at index 3

    Time Complexity: O(log n)

    Auxiliary Space: O(1)
    Please refer to the article Binary Search for more details!
     


    Binary search is a recursive algorithm. The high level approach is that we examine the middle element of the list. The value of the middle element determines whether to terminate the algorithm (found the key), recursively search the left half of the list, or recursively search the right half of the list.

    How do you write a recursive binary search in Python?

    def binary_search(my_list, low, high, elem): if high >= low: mid = (high + low) // 2 if my_list[mid] == elem: return mid elif my_list[mid] > elem: return binary_search(my_list, low, mid - 1, elem) else: return binary_search(my_list, mid + 1, high, elem) else: return -1 my_list = [ 1, 9, 11, 21, 34, 54, 67, 90 ] ...

    What is recursive binary?

    In binary recursion, the function calls itself twice in each run. As a result, the calculation depends on two results from two different recursive calls to itself.

    What is the recursive algorithm in Python?

    Recursive Functions in Python A recursive function is a function defined in terms of itself via self-referential expressions. This means that the function will continue to call itself and repeat its behavior until some condition is met to return a result.