Top 10 Programming Languages to Learn in 2019

ProgrammingPython

Binary Search in Python

In this Tutorial, we will go through the implementation of Binary Search Algorithm in Python and write an efficient python code about it. It is also known as half search method, logarithmic chop, or binary chop. Binary search works on logarithmic time in the worst case scenario making O(log(n)) comparisons, where n is the number of elements in the array, the O is Big O notation, and the log is the logarithm.

The binary search takes constant (O(1)) space, meaning that the space taken by the algorithm is the same for any number of elements in the array. It is also faster than Linear search, except small linear arrays.

Performance

  • Worst Case Performance: O(log(n))
  • Best Case Performance: O(1)
  • Average Case Performance: O(log(n))
  • Worst Case Space Complexity: O(1)

Binary Search works on sorted arrays. Large data companies like Twitter, facebook often use binary search on their hash tables to find the data quickly. The binary search algorithm works as follows:

  • Binary search begins by comparing the middle element of the array with the target value.
  • If the target value matches the middle element, its position in the array is returned.
  • If the target value is less than the middle element, the search continues in the lower half of the array.
  • If the target value is greater than the middle element, the search continues in the upper half of the array. By doing this, the algorithm eliminates the half in which the target value cannot lie in each iteration

Binary Search Pseudo Code

Let an array A with n elements with values sorted in ascending order and a target value T. The following subroutine will be used to find the index of T in A.

  1. Set L to 0 and R to n-1
  2. If L > R search is Unsuccessful
  3. Set m to the floor of ((L+R) / 2),
  4. If A[m] < T, set L = m + 1, and goto step 2.
  5. If A[m] > T, set R = m – 1, and goto step 2.
  6. If A[m] == T, Voila!! Search is done, return m
function binary_search(A, n, T):
    L := 0
    R := n − 1
    while L <= R:
        m := floor((L + R) / 2)
        if A[m] < T:
            L := m + 1
        else if A[m] > T:
            R := m - 1
        else:
            return m
    return unsuccessful

Binary Search Python Code

from math import floor

def binary_search(Array, Search_Term):
    n = len(Array)
    L = 0
    R = n-1
    
    while L <= R:
        mid = floor((L+R)/2)
        if Array[mid] < Search_Term:
            L = mid + 1
        elif Array[mid] > Search_Term:
            R = mid - 1
        else:
            return mid
    return -1


# Insert your array here
A = [1,2,3,4,7,9,12,14,18]
# term to be searched
term = 14
index = binary_search(A, term)
if index >= 0:
    print("{} is at index {}".format(A[index], index))
else:
    print("Search term not found")

Note : Array must be sorted for Binary search to work

Output

14 is at index 7

If you face any error, Please comment below. I shall be happy to help 😁

Find more variations of binary search on pyblog.in.

Related posts
Programming

Amazon Price Scraper and Auto Mailer Python App

ProgrammingPython

Top 10 Deep Learning frameworks in 2019 (with comparison)

ProgrammingPython

Python vs R - Data Visualization

Programming

Cython vs Python - Speed up your Python

2 Comments

Leave a Reply

Your email address will not be published. Required fields are marked *

Improve Your Python

...with a fresh 🐍 Python Trick 💌
code snippet every couple of days:
You can also contribute to PyBlog
Visit Contribute to Community

You have successfully subscribed to the newsletter

There was an error while trying to send your request. Please try again.

PyBlog will use the information you provide on this form to be in touch with you and to provide updates and marketing.
%d bloggers like this: