Binary search algorithm implementation in python

Binary search algorithm in python¶

In [2]:

import array as arr

​

def BinarySearch(A, s, key):

    left = 0

    right = s - 1

    while left <= right:

        mid = int (left + (right - left)/2) #Ingoring integer overflow

        if A[mid] == key:

            return mid + 1

        elif A[mid] > key:

            right = mid - 1

        else:

            left = mid + 1

    return -1

​

s = int (input('Enter the size of the array: '))

A = arr.array('i', [])

print ('Enter the elements of the array: ')

for i in range(0, s):

    element = int (input())

    A.append(element)

​

key = int(input('Enter the search value: '))

​

res = BinarySearch(A, s, key)

if res == -1:

    print (key, ' not found in the array.')

else:

    print (key, ' found at position', res)

​

​

Enter the size of the array: 5
Enter the elements of the array: 
5
10
15
20
25
Enter the search value: 25
25  found at position 5

===Time Compexity===

Best Case: O(1) Worst Case/Average Case: O(log n)