In this Tutorial, we will go through the implementation of **Binary Search Algorithm in Python** and write an efficient python code about it. It is also known as **half search method**,** logarithmic chop**, or** binary chop**. Binary search works on logarithmic time in the worst case scenario making *O(log(n))* comparisons, where n is the number of elements in the array, the O is Big O notation, and the log is the logarithm.

The binary search takes constant *(O(1))* space, meaning that the space taken by the algorithm is the same for any number of elements in the array. It is also faster than Linear search, except small linear arrays.

## Performance

**Worst Case Performance:***O(log(n))***Best Case Performance:***O(1)***Average Case Performance:***O(log(n))***Worst Case Space Complexity:***O(1)*

Binary Search works on sorted arrays. Large data companies like **Twitter, facebook**

**often use binary search on their hash tables to find the data quickly. The binary search algorithm works as follows:**

- Binary search begins by comparing the
**middle element**of the array with the target value. - If the target value matches the
**middle element**, its position in the array is returned. - If the target value is
**less than the middle element**, the search continues in the**lower half**of the array. - If the target value is
**greater than the middle element**, the search continues in the**upper half**of the array. By doing this, the algorithm eliminates the half in which the target value cannot lie in each iteration

## Binary Search Pseudo Code

Let an array **A** with **n** elements with values sorted in ascending order and a target value **T**. The following subroutine will be used to find the index of **T** in **A**.

- Set
**L**to**0**and**R**to**n-1** - If
**L > R**search is Unsuccessful - Set
**m**to the floor of**((L+R) / 2)**, - If
**A[m] < T**, set**L = m + 1**, and goto step 2. - If
**A[m] > T**, set**R = m – 1**, and goto step 2. - If
**A[m] == T**, Voila!! Search is done, return**m**

function binary_search(A, n, T): L := 0 R := n − 1 while L <= R: m := floor((L + R) / 2) if A[m] < T: L := m + 1 else if A[m] > T: R := m - 1 else: return m return unsuccessful

## Binary Search Python Code

from math import floor def binary_search(Array, Search_Term): n = len(Array) L = 0 R = n-1 while L <= R: mid = floor((L+R)/2) if Array[mid] < Search_Term: L = mid + 1 elif Array[mid] > Search_Term: R = mid - 1 else: return mid return -1 # Insert your array here A = [1,2,3,4,7,9,12,14,18] # term to be searched term = 14 index = binary_search(A, term) if index >= 0: print("{} is at index {}".format(A[index], index)) else: print("Search term not found")

Note : Array must be sorted for Binary search to work

## Output

14 is at index 7

If you face any error, Please comment below. I shall be happy to help 😁

Find more variations of binary search on pyblog.in.

Thank you for sharing excellent informations. Your web site is very cool. I’m impressed by the details that you have on this web site. It reveals how nicely you perceive this subject. Bookmarked this website page, will come back for more articles. You, my friend, ROCK! I found simply the information I already searched all over the place and just could not come across. What a perfect web-site.

Hi! This is my 1st comment here so I just wanted to give a quick shout out and tell you I genuinely enjoy reading your blog posts. Can you recommend any other blogs/websites/forums that go over the same topics? Thank you so much!

Hi, I just want know if it is possilble to get a 5 for a array like this “[ 1, 2, 3, 4, 7, 14, 14, 15, 18]” in an alternative version of this code. I’m asking you this, because I saw with this program I get 6 and, of course, the first “14” is in 5. So if we have repeated numbers the program will not prioritize them, right?!

Hey, Thanks for the comment. Actually, the program is not prioritizing the 6th index over the 5th. Just the value of the A[mid] == 6 in the 2nd iteration for your list. You can try using this modified code for your understanding.

https://ideone.com/XXhtbM