In this post, you will learn how to write a python program for binary search with a detailed explanation and algorithm so let us start from very basic.

## What is Binary Search

Binary Search is a searching algorithm to find the position of the specific element present inside a sorted array or list.

• Binary Search is also called a half-interval search.
• It is the fastest searching algorithm with time complexity of O(logn).
• Binary Search is based on a divide & conquer strategy

## Algorithm for Binary Search

NOTE: In Binary Search your list should be in sorted order (ascending order).

1. `def binarySearch(my_list,x):`(where `x` is an element that we want to find inside a list).
2. Take two-pointers `low` & `high`.
3. `low` points to the first element of the list and `high` points to the last elements of the list.
4. `while low <= high` do `mid = low + high // 2`. (`mid` gives the position of the middle element of a list)
5. `if x == my_list[mid]` then `return mid` (it gives position of `x`).
6. `elif x > my_list[mid]` then do `low = mid + 1`
7. `else `do `high = mid -1`
8. Exit from the while-loop.
9. `return -1` (this indicates that `x` is not present in the list)

Example:

From the above example and algorithm, we understood how to implement a binary search program in python but before writing a program few programming concepts you have to know.

### Source Code

``````def binarySearch(my_list,x):
low = 0
high = len(my_list) -1

while low <= high:
mid = (low+high)//2   # find mid

if x == my_list[mid]:
return mid

elif x > my_list[mid]:
low = mid+1

else:
high = mid-1

return -1

list1 = [1,2,3,4,6]

print(f"Element is present at position {binarySearch(list1,6)}")  #gives index position``````

### Output

``Element is present at position 4``

## Python Program for Binary Search using Recursion

Before writing a program you should about:

1. if-elif-else &
2. recursive function in python

### Source Code

``````def binarySearch(my_list,x,low,high):
if low <= high:
mid = (low+high)//2   # find mid

if x == my_list[mid]:
return mid

elif x > my_list[mid]:
return binarySearch(my_list,x,mid+1,high)

else:
return binarySearch(my_list,x,low,mid-1)
else:
return -1

list1 = [1,2,3,4,6]
x = 6
low = 0
high = len(list1) -1

print(f"Element is present at position {binarySearch(list1,x,low,high)}")``````

### Output

``Element is present at position 4``

Related Programs:

Hi, I'm Yagyavendra Tiwari, a computer engineer with a strong passion for programming. I'm excited to share my programming knowledge with everyone here and help educate others in this field.