本文首先介绍了二分查找法，采用“循环”和“递归”2种方法实现。采用递归算法实现了二叉树的插入和搜索算法。
一、二分查找法
查找算法的计算复杂度为O(n)、O(logN)、O(1)。
- 无序列表，顺序查找法时间复杂度为O(n)。
- 排好序的结构，O(logN)
- hash表，O(1)
二、二分查找法代码
循环方式
a = [x for x in range(100)]
target = 51
l=0
r=100
while(l<=r):
mid = (l+r)//2
if(a[mid]>target):
// 下一次循环[l,mid)
r=mid
elif(a[mid]<target):
// [mid,r)
l=mid+1
//此时命中
else:
print("target position:%d" % mid)
break
递归实现
def binarySearch(l,r,target):
mid = (l+r)//2
if(a[mid]>target):
r=mid
return binarySearch(l,r,target)
elif(a[mid]<target):
l = mid+1
return binarySearch(l,r,target)
else:
return mid
postion2 = binarySearch(0,100,50)
print(postion2) //50
postion3 = binarySearch(0,100,51)
print(postion3) //51
三、二叉树的搜索算法
在二分查找基于数组，在插入删除时需要移动较多节点，采用二叉树的数据结构，更好的实现插入、删除操作。
class BinarySearchTree2:
#在此处定义的静态变量
def __init__(self):
self.count=0
self.root = None
def count():
return self.count
def insert(self,key,value):
if(self.count == 0):
self.root = Node(key,value)
self.count = self.count+1
return
else:
node = self.root
while True:
if(node.key>key):
if(node.lnode == None):
node.lnode = Node(key,value)
return
else:
node = node.lnode
elif(node.key<key):
if(node.rnode == None):
node.rnode = Node(key,value)
return
else:
node = node.rnode
def contains(self,key):
return self._contain(self.root,key)
def _contain(self,node,key):
if(node == None):
return False
if(node.key > key):
return self._contain(node.lnode,key)
elif(node.key < key):
return self._contain(node.rnode,key)
else:
return True
四、总结
查找算法是计算机中的基本问题，无论面试还是在日常工作中，都会经常遇到查找问题。本文，根据二分搜索算法用Python实现二叉树。
