Python Binary Search

  1. Binary Search Algorithm
  2. Python Program for Binary Search
Note

If you want to understand Binary Search in detail then refer to the binary search algorithm article.

Binary Search Algorithm

Let us assume that we have an unsorted array A[] containing n elements, and we want to find an element X.

  • Set lo as 0 and hi as n - 1.
  • While lo < hi, set mid = lo + (hi - lo)/2.
    • If A[mid] == X , we have found the element return the indexmid.
    • If A[mid] < X ,then discard the left half of elements and set lo as mid+1.
    • Else if A[mid] > X, then discard the right half of elements and set hi asmid-1.
  • Element is not found, so return -1.
def binary_search(arr, x, n):
    lo = 0
    hi = n - 1
    mid = 0

    while lo <= hi:
        mid = (hi + lo) // 2
        if arr[mid] < x:
            lo = mid + 1
        elif arr[mid] > x:
            hi = mid - 1
        else:
            return mid
    return -1
    
arr = [ 2, 3, 4, 1, 5 ]
x = 4
n = len(arr)
result = binary_search(arr, x ,n)

if result == -1:
    print("Element not found")
else:
    print("Element is present at index", str(result))

Output:

Element is present at index 2
Contribute
DelftStack is a collective effort contributed by software geeks like you. If you like the article and would like to contribute to DelftStack by writing paid articles, you can check the write for us page.

Related Article - Python Algorithm

  • Linear Search in Python