Binary Search Python – Searching Algorithm

Binary Search Python is an optimized search algorithm to find a variable in an Ordered array or list.

Suppose I have to find supercalifragilisticexpialidocious in a dictionary:

  • Dictionary is an ordered list. (A-Z)
  • I will not find the word in the start because its starting character is not A.
  • Suppose I open a page randomly in middle and it appears that the words are all from M.
  • I knew that I have to go forward and eventually I find the Word.

It’s just like the Same how Binary Search Python works. It Starts from the middle and works accordingly. To know more about the Algorithm Visit HERE

binary-search-python

How Binary Search Python works

A binary search is an algorithm that takes as input sorted list of items. It returns the location of an element you’re seeking if it’s in that list. Otherwise, it returns null.
How to implement binary search in Python?
Let’s do this example with Arrays
Note: Array may hold succession of elements in row of successive buckets.
The buckets are numbered from to the size you allocated, first bucket = 0, 2nd = 1 then numbers go on. So in order to write the function for binary search, we want two parameters, first the item we are searching for, and 2nd the array in which we are searching. Each time we have to check the middle element and act accordingly. Suppose we are searching for 7 in an ordered array of elements containing 1 to 10. The middle element in 1 to 10 = 5, now we will reduce the over searching array from 5 to 10. Finding the middle element 5 to 10 = 8, reducing further to 5-8 and eventually we find 7. 

Complete Code

def bsearch(array, x):
               start = 0
               end = len(array)—1
               while start <= end:
                         mid = (start + end)/2
                         guess = array[mid]
                         if guess == x:
                             return mid
                         if guess > x:
                             end = mid - 1
                         else:
                             start = mid + 1
               return None

 

READ MORE

Algorithms related posts visit HERE

Data Structures related posts visit HERE

Databases related posts Visit HERE

Python-related posts Visit HERE

C++ related posts Visit HERE

Data Science related posts visit HERE

Share the Knowledge