Python program to implement Binary Search Algorithm

Hello everyone! Welcome back to programminginpython.com. Here in this post am going to show you how to implement binary search algorithm in python. In the previous post, I discussed Linear Search Algorithm which is a very basic search algorithm here I will discuss Binary Search.

Binary Search as the name suggests binary, here the list is divided into halves and then searched in each half. One notable thing about this binary search is that the list should be sorted first before executing the algorithm. The list is divided into two halves by the index, find the mid element of the list and then start to mid-1 is one list and mid+1 to end is another list, check if the element is mid, greater than it or less than it and return the appropriate position of the key element to be found.

You can also watch the video on YouTube here

Program on Github

Binary Search Algorithm – Code Visualization

Time Complexity

Best Case O(1)
Average Case O(log n)
Worst Case O(log n)

Program on Github

Algorithm

Given a list L of n elements with values or records L0, L1, …, Ln-1, sorted in ascending order, and given key/target value K, binary search is used to find the index of K in L

  1. Set a variable start to 0 and another variable end to n-1(size of the list)
  2. if start > end break the algorithm, as it works only on sorted lists
  3. calculate mid as (start + end)/2
  4. if the key element is
    1. equal to mid, the search is done return position of mid
    2. greater than mid, set start to mid + 1 and repeat from step 2
    3. less than mid, set end to mid - 1 and repeat from step 2

Program

Program on Github

Output

Binary Search Algorithm - programminginpython.com
Binary Search Algorithm – programminginpython.com
Binary Search Algorithm - programminginpython.com
Binary Search Algorithm – programminginpython.com
Binary Search Algorithm - programminginpython.com
Binary Search Algorithm – programminginpython.com

Feel free to look at some other algorithms here or some programs on lists here or have a look at all the programs on python here.

Same algorithm in other programming languages

In C language: http://www.mycodingcorner.com/2015/01/c-binary-search.html

In CPP languagehttp://www.mycodingcorner.com/2015/03/cpp-program-for-implementing-binary-search.html

In Java languagehttp://www.mycodingcorner.com/2015/01/java-binary-search.html

Leave a Reply