What is Binary Search Algorithm in python?

Today, we will learn about binary search algorithm in python. Binary search applies to the sorted array or to a larger size list. The complexity of O (log n) time makes it much faster compared to other sorting algorithms. The only limitation is that the list or item list must be sorted in order to use the binary search algorithm.

Binary search looks for a particular item by comparing the middlemost item of the collection. If a match occurs, then the index of the item is return. If the middle item is greater than the item, then the item is search in the sub-array to the left of the middle item. Otherwise, the item is searched for in the sub-array to the right of the middle item. This process continues on the sub-array as well until the size of the subarray reduces to zero.

How Binary Search Works?

For a binary search to work, the target list must be sorted. We will learn the binary search process with a symbolic example. The following is our sorted array and let’s imagine we need to search the location of value 99 using a binary search algorithm.

First, we shall determine half of the array by using this formula −

mid =( beg + last ) / 2

Here it is, (0 + 9 ) / 2 = 4 (integer value of 4.5). So, 4 is the mid of the array.

Now we compare the value stored at location 4, with the value being searched, i.e. 99. We find that the value at location 4 is 55, which is not a match. As the value is greater than 55 and we have a sorted array, so we also know that the target value must be in the upper portion of the array.

We change our beg to mid + 1 and find the new mid value again.

beg= mid + 1

mid =( beg + last ) / 2

mid=(5 + 9) / 2 =7

Our new mid is 7 now. We compare the value stored at location 7 with our target value 99.

The value stored at location 7 is not a match, rather it is more than what we are looking for. so we also know that the target value must be in the upper portion of the array.

We change our beg to mid + 1 and find the new mid value again.

beg= mid + 1

mid =( beg + last ) / 2

mid=(8 + 9) / 2=8

Our new mid is 8 now. We compare the value stored at location 8 with our target value 99.

We find that it is a match.We conclude that the target value 99 is stored at location 8.

Now second Example let’s imagine we need to search the location of value 22.

beg=0 and last=9

mid=(0 + 9) / 2 = 4

Here mid is 4 now. We compare the value stored at location 4 with our target value 22. its not match

so last= mid – 1

beg=0 and last =4 – 1

mid=(0 + 3 ) / = 1

Here mid is 1 now. We compare the value stored at location 1 with our target value 22. its match

Features of binary Search algorithm

1.Binary search is a fast search algorithm. This search algorithm works on the principle of divide and conquer.

2.It is faster than sequential search

3.It reduces the span of searching the value

4.Best Case :CBest(n)=1

5.Worst Case :CWorst(n)=O(logn)

6.Average Case :CAvg(n)=O(logn)

Implementing Binary Search Algorithm 

Following are the steps of implementation that we will be following:

1. Start with the middle element:
   • Here If the target value is equal to the middle element of the array, then return the index of the middle element.
   • If not, then compare the middle element with the target value,
     • If the target value is greater than the number in the middle index, then pick the elements to the right of the middle index, and start with Step 1.
     • else if the target value is less than the number in the middle index, then pick the elements to the left of the middle index, and start with Step 1.
2. When a match is found, return the index of the element matched.
3. If no match is found, then return Element is not Found

def binarySearch(arr,item):
    beg=0
    last=len(arr)-1
    while beg<=last:
        mid = (beg + last) // 2
        if item==arr[mid]:
            return mid
        if item>arr[mid]:
            beg=mid+1
        else:
            last=mid-1
    else:
        return False
arr=[]
arr_size=int(input("Enter The Size Of the Array: "))
for i in range(arr_size):
    arr_element=int(input("Enter The The Element in Acceding order At "+str(i)+" : "))
    arr.append(arr_element)

item=int(input("Enter Element You Want To Search: "))
result=binarySearch(arr,item)
if result:
    print(f"Element Found In {result}")
else:
    print("Element is not Found")

Full source code: