Binary Search algorithm.

Binary Search use case.


In computer science binary search is a search algorithm that finds the position of a target element within a sorted array. Binary search is also called half-interval search, logarithmic search, or binary chop. Binary search compares the target element's value to the middle element of the array (list). If elements are not equal, the half in which the target cannot belong is eliminated and the search continues on the remaining half, also taking the middle element to compare to the target value.

Binary Search algorithm.



The process goes on until the target element is found. If the search finishes with empty remaining half, the target is not in the array.

Binary Search Algorithm can have 2 implementations:

- Iterative Method.
- Recursive Method.


Binary Search Python code - Iterative Method:




def binary_Search(array, x, low, high):

    # Repeating until the pointers low and high meet
    while low <= high:

        mid = low + (high - low)//2

        if array[mid] == x:
            return mid

        elif array[mid] < x:
            low = mid + 1

        else:
            high = mid - 1

    return -1


array = [3, 5, 4, 0, 12, 11]
x = 12

result = binary_Search(array, x, 0, len(array)-1)

if(result == -1):
    print("Searched element not found")
else:
    print("Searched element found at index: ", result)

OUT: Searched element found at index: 4



Binary Search Python code - Recursive Method:



def binary_Search(array, x, low, high):

    if high >= low:

        mid = low + (high - low)//2

        # If found at mid, then return it
        if array[mid] == x:
            return mid

        # Search the left half
        elif array[mid] > x:
            return binary_Search(array, x, low, mid-1)

        # Search the right half
        else:
            return binary_Search(array, x, mid + 1, high)

    else:
        return -1


array = [3, 5, 4, 0, 12, 11]
x = 12

result = binary_Search(array, x, 0, len(array)-1)

if(result == -1):
    print("Searched element not found")
else:
    print("Searched element found at index: ", result)

OUT: Searched element found at index: 4





See also related topics: