Python Program to Perform Binary Search

In this tutorial, you will learn how Binary Search sort works with example.

The Binary Search is a fundamental searching algorithm for finding an element's position in a sorted array. While finding element it always approach for middle element.

Binary Search Algorithm can be implemented in two ways:

1. Iterative Binary Search
2. Recursive Binary Search

Example 1 : Iterative Binary Search

    
# python program to iterative binary search

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

    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 = [1,2,3, 4, 5, 6, 7, 8, 9,10]
x = int(input('Enter Element to Search ::'))

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

if result != -1:
    print("Element Found at index " + str(result))
else:
    print("Element Not found")
       

Output :

    
//Output - 1
Enter Element to Search ::12
Element Not found

//Output - 2
Enter Element to Search ::6
Element Found at index 5
    

Example - 2 : Recursive Binary Search

    
# python program to recursive binary search

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

    if high >= low:

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

        if array[mid] == x:
            return mid

        elif array[mid] > x:
            return binarySearch(array, x, low, mid-1)

        else:
            return binarySearch(array, x, mid + 1, high)

    else:
        return -1


array = [1,2,3, 4, 5, 6, 7, 8, 9,10]
x = int(input('Enter Element to Search ::'))

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

if result != -1:
    print("Element Found at index " + str(result))
else:
    print("Element Not found")
       

Output :

    
Enter Element to Search ::7
Element Found at index 6
    

In both method searching algorithm start from mid and check middle element is the search element or not. If middle element is search element then it return found message else it again check that search element is less than or greater than from mid. As per comparison, it set a new middle point and repeat process till an element is found or till low point and high point meet.