Python Binary Search

  2. HowTo
  3. Python How-To's
  4. Python Binary Search
Harshit Jindal Oct 10, 2023
Python Python Algorithm
  1. Binary Search Algorithm
  2. Python Program for Binary Search
Python 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 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
Author: Harshit Jindal
Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

Related Article - Python Algorithm