Python Binary Search

Python Binary Search

Harshit Jindal Mar-30, 2021 Feb-19, 2021 Python Python Algorithm
  1. Binary Search Algorithm
  2. Python Program for Binary Search
<div class="panel panel-primary panel-warning">
<div class="panel-heading">Note</div>
<div class="panel-body">

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 index mid.
    • 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 as mid-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

Related Article - Python Algorithm

  • Smith-Waterman Algorithm in Python
  • Rabin-Karp Algorithm in Python
  • Union-Find Algorithm in Python
  • Depth-First Search in Python
  • Sieve of Eratosthenes in Python
  • Linear Search in Python