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).

(where`def binarySearch(my_list,x):`

is an element that we want to find inside a list).**x**- Take two-pointers

&**low**.`high`

points to the first element of the list and`low`

points to the last elements of the list.`high`

do`while low <= high`

. (`mid = low + high // 2`

gives the position of the middle element of a list)`mid`

then`if x == my_list[mid]`

(it gives position of`return mid`

).`x`

then do`elif x > my_list[mid]`

`low = mid + 1`

do`else`

`high = mid -1`

- Exit from the while-loop.
(this indicates that`return -1`

is not present in the list)`x`

**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:

- if-elif-else &
- 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: