Python program for binary search

Do you know how to do a Binary Search in Python? Let’s discuss and understand how to code the algorithm with examples. Also, we will cover the following given topics.

• Python program for binary search
• Python program for binary search recursive and iteration
• Python Program for binary Search tree
• Python Program for Binary Search recursive
• Python Program for binary tree traversal
• Python Program to implement binary search without recursion
• Python Program for binary addition

Python program for binary search

• In this section, we will how to write a Program for binary Search in Python.
• To locate a specific element in the list, use a binary search technique. Let’s say we need to get the index position of a specific element in a list of 1,000 elements. The binary search algorithm makes determines the element’s index position.
• The list’s entries must be sorted in order to apply the binary search technique. Sort the components first if they aren’t already sorted. There are two methods we can use for binary search; they are explained below.
  • Iterative method
  • Recursive method

The recursive method comes after the divide and conquers strategy. This method repeatedly calls a function until it locates an entry in the list.

The iterative approach finds the index location of an element by repeatedly repeating a number. To complete this process, the while loop is utilized.

Let’s go through a binary search implementation step by step. We are looking for the index position of 82 in a list of elements that has been sorted.

Here is the list:

[17,92,67,14,82,34]  

Now we will consider two points in our list the first one is represented as low the smaller value and the second value will be higher.

mid = (low+high)/2  
Here, the low is 0 and the high is 6.  
mid = (0+6)/2  
mid = 3   

• We will now match the searched element with the midpoint of the index. 14 does not equal 82 in this situation. In order to locate the element, we must compare two more things.
• Return mid if the number we are looking for is equal to the midpoint; else, move on to the next comparison.
• Since the number to be searched is the middle number, we set low to be equal to mid + 1 and compare n with the middle element of the components on the right side of mid.

Example:

Let’s take an example and check how to create a binary Search Program in Python.

def new_binary_val(new_list, target_val, low, high):

    while low <= high:

        mid = low + (high - low)//2

        if new_list[mid] == target_val:
            return mid

        elif new_list[mid] < target_val:
            low = mid + 1

        else:
            high = mid - 1

    return -1

new_list = [17, 89, 45, 28, 95, 13, 88]
target_val = 28
#Display the list
print("The input list is", new_list)

print("Value to be found is ", target_val)

index = new_binary_val(new_list, target_val, 0, len(new_list)-1)

if index != -1:
    print("The Index of the value is " + str(index))
else:
    print("Value Not found")

Here is the implementation of the following given code

This is how we can create a program for binary search in Python.

Read How to find perfect number in Python

Python program for binary Search (recursive and iteration)

• Finding an item’s location in a sorted array using a binary search in Python. Lists are split in two by it. When a value is entered, the search is narrowed to the right side of the list if it is greater than the middle number. If not, the number on the left of the list is the one the search looks and for this, we are going to use the recursive method.
• This approach involves iterating through the entire list while repeating a set of directives. We’ll keep looking till we locate the median value.
• Implement a function called binary search() that takes four parameters (array, low, high, a).
• Declare two variables to hold the list’s greatest and lowest values.
• Then Continue with step 4 until the lowest and highest are met:
• mid=(low + high) / 2 Assuming (a == arr[mid]) return mid if (a > arr[mid]), otherwise If an is on the right side, low equals mid+1, and if an is on the left, high equals mid-1,
• Set up the array and the element to be searched from every number.
• If the element is found, print the result position; else, print. It was not located. 

Example:

Let’s take an example and check how to create a binary search program in Python by using the recursive method.

Source Code:

def search_val(new_list, low, high, m):
 
    
    if high >= low:
        mid = (high + low) // 2
 
        
        if new_list[mid] == m:
            return mid
 
        elif new_list[mid] > m:
            return search_val(new_list, low, mid - 1, m)
 
        else:
            return search_val(new_list, mid + 1, high, m)
 
    else:
        return -1

new_list = [ 18, 98, 27, 18, 45, 91, 29, 20]
m = 18

result = search_val(new_list, 0, len(new_list)-1, m)
 
if result != -1:
    print("The Index of the value is", str(result))
else:
    print("Value Not found")

You can refer to the below Screenshot

As you can see in the Screenshot we have understood how to write a program for binary search recursive and iteration method.

Read How to reverse a number in Python

Python Program for binary Search tree

• A specific type of data structure called a tree is used to represent data in a hierarchical format. It can be described as a group of nodes collections of things or entities that are connected to one another to create the illusion of a hierarchy. Trees are non-linear data structures because their data is not organized in a linear or sequential manner.
• A binary tree is a collection of finite nodes that may or may not have elements. Three entities make comprise a node. a value with two left and right pointers. Each subtree’s parent component is the root node.
• It may alternatively be thought of as the tree’s root node. Children are the nodes that are connected to the parent element. On the other hand, the fundamental components of a binary tree are leaf nodes.

Example:

class BinaryTreeNode:
  def __init__(self, data):
    self.data = data
    self.leftChild = None
    self.rightChild=None
     
def insert(root,newValue):
    if root is None:
        root=BinaryTreeNode(newValue)
        return root
    if newValue<root.data:
        root.leftChild=insert(root.leftChild,newValue)
    else:
        
        root.rightChild=insert(root.rightChild,newValue)
    return root
def findLargestElement(root):
    if root==None:
        return False
    elif root.rightChild==None:
        return root.data
    else:
        return findLargestElement(root.rightChild)
root= insert(None,15)
insert(root,22)
insert(root,67)
insert(root,87)
insert(root,34)
insert(root,18)
insert(root,94)
print("Largest Element is:")
print(findLargestElement(root))

Here is the Screenshot of the following given code

In this example, we have understood how to write a Program for a binary Search tree.

Read Python Program for even or odd

Python Program for Binary Search (recursive)

• The recursion strategy can be utilized in binary search. As long as the requirement isn’t satisfied, the recursive function will keep calling itself.
• The divide and conquer strategy, which is used in the recursive approach, divides a difficult problem into smaller subproblems, solves those, and then combines them to produce the desired answer.

Example:

Let’s take an example and check how we can create a program for binary search in Python by using the recursive method.

Source Code:

def new_binary_val(new_list, target_val, low, high):

    while low <= high:

        mid = low + (high - low)//2

        if new_list[mid] == target_val:
            return mid

        elif new_list[mid] < target_val:
            low = mid + 1

        else:
            high = mid - 1

    return -1

new_list = [17, 89, 45, 28, 95, 13, 88]
target_val = 28
#Display the list
print("The input list is", new_list)

print("Value to be found is ", target_val)

index = new_binary_val(new_list, target_val, 0, len(new_list)-1)

if index != -1:
    print("The Index of the value is " + str(index))
else:
    print("Value Not found")

Here is the implementation of the following given code

Read: Python Extend Vs Append

Python Program for binary tree traversal

• A tree’s nodes must all be visited in order to be traversed. For instance, you might wish to identify the largest value or add all the values in the tree. You must travel to each node of the tree in order to do these operations.
• A tree is an abstract data structure that is implemented in numerous programming languages, and traversing implies visiting. Comparing the implementation of trees to that of arrays or lists, it is non-linear in nature.
• A traversal method is used to visit every node in a tree and print its values. Iterating over each node in a tree is a necessary part of traversal. Since every node is connected via an edge, we always begin at the root (head).
• There are three methods of traversals that can be executed for a tree data structure.
  • Inorder tree traversal
  • Preorder tree traversal
  • Postorder tree traversal
• Now let’s briefly discuss these three ways to traverse trees in Python.
  • Inorder tree traversal: In the inorder traversal, we first visit the current node’s left child or left subtree, followed by the current node, and finally the right child or right subtree of the current node. Until all of the nodes have been traversed, we repeat this step.
  • Preorder tree traversal: This approach starts by visiting the root node, followed by traversing the left subtree, and finishing with the right subtree.
  • Postorder tree traversal: In this case, the root node is traversed and the left side is visited first and then the right side sub-tree is traversed.

Example:

Let’s take an example and implementation of traversing in Python by using inorder, preorder, and postorder.

Source Code:

class Node:
    def __init__(self, element):
        self.left = None
        self.right = None
        self.val = element

def inorder(root):

    if root:
        inorder(root.left)
        print(str(root.val) + ":-", end='')
        inorder(root.right)

def postorder(root):

    if root:
        postorder(root.left)
        postorder(root.right)
        print(str(root.val) + ":-", end='')


def preorder(root):

    if root:
        print(str(root.val) + ":-", end='')
        preorder(root.left)
        preorder(root.right)


root = Node(8)
root.left = Node(9)
root.right = Node(10)
root.left.left = Node(11)
root.left.right = Node(12)

print("Inorder traversal ",inorder(root))

print("Preorder traversal ",preorder(root))

print("Postorder traversal ",postorder(root))

Here is the Screenshot of the following given code

Read Complex Numbers in Python

Python Program to implement binary search without recursion

• In this example, we will implement a program of binary search without the recursion method. So, in this case, we will use the iterative process.
• The iterative approach finds the index location of an element by repeatedly repeating a number. To complete this process, the while loop is utilized.
• In this example, we will consider the following list on which the search is implemented. Assume let the value to be found is m= 79. Now we will take two pointers the low to the smallest position in the list and the high to the highest position in the list.
• If the mid element and the element to be searched match, we shall compare the mid element with the matching element and return the mid element.
• We shall set the low pointer to the “middle+1” element and rerun the process if the element to be sought is larger than the mid.
• The high pointer will be moved to the “middle-1” element and the method will be repeated if the element to be sought is lower than the mid element.

Example:

def new_Search_val(new_list, m, low, high):
   
    while low <= high:
        middle = low + (high - low)//2
        if new_list[middle] == m:
            return middle
        elif new_list[middle] < m:

            low = middle + 1
        else:

            high = middle - 1
    return -1

new_list = [27, 95, 14, 79, 11]

m = 79
new_output = new_Search_val(new_list, m, 0, len(new_list)-1)

if new_output != -1:

    print("Value is found at index ",new_output)

else:

    print("Value is Not found")

Here is the execution of the following given code

Read Python Palindrome Program With Examples

Python Program for binary addition

• In this section, we will discuss how to add two binary addition in Python.
• For this, we are going to use the int() function In the example below, we are converting the string (which is a binary value) into an integer number hence we are passing the base value as 2.
• The int() method translates the given string into an integer number taking into account the provided base value (binary numbers have base 2, decimals have base value 10).
• The Python function bin() transforms an integer to the equivalent binary representation. This produces a string that includes the prefix (0b) to indicate that it was converted to a binary format.

Example:

val_binary = '01010'
num_bin = '11111'

result = int(val_binary, 2) + int(num_bin, 2)
result = bin(result)

print(result)

Here is the Screenshot of the following given code

This is how we can add two binary numbers in Python by using the int() function.

In this article, we have discussed how to do a Binary Search in Python. Let’s discuss and understand how to code the algorithm with examples. Also, we will cover the following given topics.

• Python program for binary search
• Python program for binary search (recursive and iteration)
• Python Program for binary Search without function
• Python Program for binary Search tree
• Python Program for Binary Search (recursive)
• Python Program for binary tree traversal
• Python Program to implement binary search without recursion
• Python Program for binary addition

You may like the following Python tutorials:

• Armstrong number in Python
• Python program for bubble sort
• Python program for a diamond pattern
• How to split a string using regex in python
• Python Dictionary Methods
• How to convert an integer to string in python
• Unexpected EOF while parsing Python