Binary search algorithm which is also known as the logarithmic algorithm is an algorithm and it is used in finding an item from the sorted array. The binary search algorithm is faster than a linear search algorithm. Make sure you remember that the array must be sorted for the algorithm to work. You will understand why the array should be sorted as you go through the article.

A sorted array with 9 elements

Let us consider a sorted array of length N. Assume three indices one is the left index(L), one is the right index(R), and the middle index (M) is the floor value of (L+R)/2. For example, if L+R is 9, then the value of 9/2 is 4.5 and the floor value is 4.

Steps:

To make it short there are only three cases that can occur when you search for an element in an array which is given below:

Move the left and right pointer based on the situation you encounter and know when to stop (L > R).

Python Code for Binary Search Algorithm.

import math
def search(val, arr ):
n = len(arr)
l = 0
r = n-1
while l<=r:
m = math.floor((l+r)/2)
if val==arr[m]:
return m
elif val<arr[m]:
r = m-1
elif val>arr[m]:
l = m+1
return "not found"
print(search(4, [0, 1, 2, 3, 4]))

Complexity:

The worst case complexity of the linear search is O(n) because you have to search through the whole array when the element you search is at the end of an array. The worst case complexity of the binary search is O(log n) because the search space is reduced everytime when you search through the array.

Interesting Info: https://www.codementor.io/@ashwanitr001/is-your-binary-search-bug-free-16ptximygu