Question

Python 3! Please provide detailed information and screenshots!

This is a practice for you to discuss an implementation of a BST (Binary Search Tree) in a real-life scenario or real business scenario.

What to submit?

1. An introduction with a title of what is the implementation

2. A diagram or design of how the BST is implemented in your scenario

3. Simple explanation of the implementation

4. Can you make it as an application in Python. Yes/No. If Either Yes or No. What it takes to implement or What are the complexities involved.

5. Design of the application - Write down (not the code) design of Data Collection, Storage of data, OOP design of Application, Pseudo Code of the Design or flow chart, UML diagram.

Answer 1

Ans 1.>

In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array.Binary search compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found. If the search ends with the remaining half being empty, the target is not in the array.

Ans.2>

This is the diagram of how Binary search works

Ans.3>

Binary Search Tree is a node-based binary tree data structure which has the following properties:

The left subtree of a node contains only nodes with keys lesser than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
The left and right subtree each must also be a binary search tree.

Ans.4>

Yes, We can definately make an application of Binary search in python

following is an example

Problem statement − We will be given a sorted list and we need to find an element with the help of a binary search.

Algorithm
Compare x with the middle element.

If x matches with the middle element, we return the mid index.

Else If x is greater than the mid element, then x can only lie in right half subarray after the mid element. So we recur for the right half.

Else (x is smaller) recur for the left half

Recursive Algorithm

def binarySearchAppr (arr, start, end, x):
# check condition
if end >= start:
   mid = start + (end- start)//2
   # If element is present at the middle
   if arr[mid] == x:
      return mid
   # If element is smaller than mid
   elif arr[mid] > x:
      return binarySearchAppr(arr, start, mid-1, x)
   # Else the element greator than mid
   else:
      return binarySearchAppr(arr, mid+1, end, x)
   else:
   # Element is not found in the array
      return -1
arr = sorted(['t','u','t','o','r','i','a','l'])
x ='r'
result = binarySearchAppr(arr, 0, len(arr)-1, x)
if result != -1:
   print ("Element is present at index "+str(result))
else:
print ("Element is not present in array")