Example 1: 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
Example 2: 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);
}
}
Example 3: 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 datacur_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 datacur_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())
Example 4: binary search in python
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
Example 5: 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)
Example 6: dichotomic search c++
using namespace std;
// A recursive binary search function. It returns
// location of x in given array arr[l..r] is present,
// otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l) {
int mid = l + (r - l) / 2;
// If the element is present at the middle
// itself
if (arr[mid] == x)
return mid;
// If element is smaller than mid, then
// it can only be present in left subarray
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
// Else the element can only be present
// in right subarray
return binarySearch(arr, mid + 1, r, x);
}
// We reach here when element is not
// present in array
return -1;
}
int main(void)
{
int arr[] = { 2, 3, 4, 10, 40 };
int x = 10;
int n = sizeof(arr) / sizeof(arr[0]);
int result = binarySearch(arr, 0, n - 1, x);
(result == -1) ? cout << "Element is not present in array"
: cout << "Element is present at index " << result;
return 0;
}