27.4 C
Gujarat
HomeAlgorithmsBinary Search Algorithm in python

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.
Binary Search Algorithm in python 1

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.

Binary Search Algorithm in python2
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.

Binary Search Algorithm in python 3
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.

Binary Search Algorithm in python 4

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

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:

https://repl.it/@PatelRohan/binary-search#main.py

RELATED ARTICLES

3 COMMENTS

  1. Appreciating the persistence you put into your blog and detailed information you present.
    It’s nice to come across a blog every once in a while that isn’t the same
    old rehashed information. Great read! I’ve bookmarked your
    site and I’m including your RSS feeds to my Google account.

  2. hey there and thank you for your info – I’ve definitely picked up anything new from right here.
    I did however expertise some technical issues using this website, as I
    experienced to reload the website lots of times previous to I
    could get it to load correctly. I had been wondering if your web hosting is OK?
    Not that I’m complaining, but slow loading instances times will very frequently affect your placement in google and can damage your quality score if
    advertising and marketing with Adwords. Well I’m adding this RSS to my e-mail and can look out for a lot more
    of your respective interesting content. Make sure you update this again soon.

LEAVE A REPLY

Please enter your comment!
Please enter your name here

15,000FansLike
5,000FollowersFollow
535FollowersFollow
- Advertisment -spot_img

Subscribe to our newsletter

To be updated with all the latest news, offers and special announcements.

Most Popular