# Python Binary Search

Harshit Jindal Mar-30, 2021 Feb-19, 2021 Python Python Algorithm
``````<div class="panel panel-primary panel-warning">
<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`.

• ##### 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:
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