What is Binary Search in Python?
There are following 3 ways to implement binary search in Python, but the basic idea behind all implementations is the same. Here are a few examples:
Binary Search in Python using Recursive implementation:
def binary_search(arr, x, low, high):
if low > high:
return -1
mid = (low + high) // 2
if arr[mid] == x:
return mid
elif arr[mid] > x:
return binary_search(arr, x, low, mid-1)
else:
return binary_search(arr, x, mid+1, high)
Binary Search in Python using Iterative implementation:
def binary_search(arr, x):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == x:
return mid
elif arr[mid] > x:
high = mid - 1
else:
low = mid + 1
return -1
Binary Search in Python Using the bisect module in Python:
import bisect
def binary_search(arr, x):
index = bisect.bisect_left(arr, x)
if index != len(arr) and arr[index] == x:
return index
else:
return -1
Note that third implementation uses the built-in bisect module in Python which provides efficient way to find the insertion point of a value in a sorted list.
Explore More Programming Challenges:
Python References: