Answers for "binary search algorithm python"

python binary search

def binary_search(arr, item):
	first = 0
	last = len(arr) - 1
	while(first <= last):
		mid = (first + last) // 2
		if arr[mid] == item :
			return True
		elif item < arr[mid]:
			last = mid - 1
		else:
			first = mid + 1	
	return False

iterative binary search python

def binary_search(a, key):
	low = 0
	high = len(a) - 1
	while low < high:
		mid = (low + high) // 2
		if key == a[mid]:
			return True
		elif key < mid:
			high = mid - 1
		else:
			low = mid + 1

	return False

binary search java

// Java implementation of iterative Binary Search 
class BinarySearch { 
	// Returns index of x if it is present in arr[], 
	// else return -1 
	int binarySearch(int arr[], int x) 
	{ 
		int l = 0, r = arr.length - 1; 
		while (l <= r) { 
			int m = l + (r - l) / 2; 

			// Check if x is present at mid 
			if (arr[m] == x) 
				return m; 

			// If x greater, ignore left half 
			if (arr[m] < x) 
				l = m + 1; 

			// If x is smaller, ignore right half 
			else
				r = m - 1; 
		} 

		// if we reach here, then element was 
		// not present 
		return -1; 
	} 

	// Driver method to test above 
	public static void main(String args[]) 
	{ 
		BinarySearch ob = new BinarySearch(); 
		int arr[] = { 2, 3, 4, 10, 40 }; 
		int n = arr.length; 
		int x = 10; 
		int result = ob.binarySearch(arr, x); 
		if (result == -1) 
			System.out.println("Element not present"); 
		else
			System.out.println("Element found at "
							+ "index " + result); 
	} 
}

python code for binary search tree

#Complete Binary Search Tree Using Python 3

class node:
    def  __init__(self,data):
        self.data=data
        self.left=None
        self.right=None

class binarytree:
    def __init__(self):
        self.root=None

#INSERT

    def insert(self,data):
        if self.root==None:				
            self.root=node(data)
        else:
            self._insert(data,self.root)
    def _insert(self,data,cur_node):
        if data<cur_node.data:
            if cur_node.left==None:			
                cur_node.left=node(data)
            else:
                self._insert(data,cur_node.left) 
        elif data>cur_node.data:			
            if cur_node.right==None:
                cur_node.right=node(data)
            else:
                self._insert(data,cur_node.right)
        else:
            print('Data In Treee Already')

#REMOVE

    def remove(self,data):
        if self.root!=None:
            self._remove(data,self.root)
    def _remove(self,data,cur_node):
        if cur_node == None:
            return cur_node
        if data<cur_node.data:
            cur_node.left=self._remove(data,cur_node.left)
        elif data>cur_node.data:
            cur_node.right=self._remove(data,cur_node.right)
        else:
            if cur_node.left is None and cur_node.right is None:
                print('Removing Leaf Node')
                if cur_node==self.root:
                    self.root=None
                del cur_node
                return None
            if cur_node.left is None:
                print('Removing None with Right Child')
                if cur_node==self.root:
                    self.root=cur_node.right
                tempnode=cur_node.right
                del cur_node
                return tempnode
            elif cur_node.right is None:
                print('Removing None with Left Child')
                if cur_node==self.root:
                    self.root=cur_node.left
                tempnode=cur_node.left
                del cur_node
                return tempnode
            print('Removing Node with 2 Children')
            tempnode=self.getpred(cur_node.left)
            cur_node.data=tempnode.data
            cur_node.left=self._remove(cur_node.data,cur_node.left)
        return cur_node
    def getpred(self,cur_node):
        if cur_node.right!=None:
            return self.getpred(cur_node.right)
        return cur_node

#INORDER TRAVERSAL

    def inorder(self):
        if self.root!=None:
            self._inorder(self.root)
    def _inorder(self,cur_node):
        if cur_node!=None:
            self._inorder(cur_node.left)
            print(cur_node.data)
            self._inorder(cur_node.right)

#PREORDER TRAVERSAL

    def preorder(self):
        if self.root!=None:
            self._preorder(self.root)
    def _preorder(self,cur_node):
        if cur_node!=None:
            print(cur_node.data)
            self._preorder(cur_node.left)
            self._preorder(cur_node.right)

#POSTORDER TRAVERSAL

    def postorder(self):
        if self.root!=None:
            self._postorder(self.root)
    def _postorder(self,cur_node):
        if cur_node!=None:
            self._postorder(cur_node.left)
            self._postorder(cur_node.right)
            print(cur_node.data)

#MINIMUM VALUE

    def minval(self):
        if self.root!=None:
            return self._minval(self.root)
    def _minval(self,cur_node):
        if cur_node.left!=None:
            return self._minval(cur_node.left)
        return cur_node.data

#MAXIMUM VALUE

    def maxval(self):
        if self.root!=None:
            return self._maxval(self.root)
    def _maxval(self,cur_node):
        if cur_node.right!=None:
            return self._maxval(cur_node.right)
        return cur_node.data

tree=binarytree()

tree.insert(100)
tree.insert(90)					#			 100
tree.insert(110)				#			/	\
tree.insert(95)					#          90   110
tree.insert(30)					#		  /  \
								#		30    95 
tree.remove(110)
tree.remove(90)

tree.inorder()
#tree.preorder()
#tree.postorder()

print(tree.minval())
print(tree.maxval())

binary search python

# This is real binary search
# this algorithm works very good because it is recursive

def binarySearch(arr, min, max, x):
    if max >= min:
        i = int(min + (max - min) / 2) # average
        if arr[i] == x:
            return i
        elif arr[i] < x:
            return binarySearch(arr, i + 1, max, x)
        else:
            return binarySearch(arr, min, i - 1, x)

python binary search program

#grepper

def binary_search(item_list,item):
	first = 0
	last = len(item_list)-1
	found = False
	while( first<=last and not found):
		mid = (first + last)//2
		if item_list[mid] == item :
			found = True
		else:
			if item < item_list[mid]:
				last = mid - 1
			else:
				first = mid + 1	
	return found