针对序列已经排好序了，以从小到大排好的序列为例，每次取中间的元素和待查找的元素比较，如果中间的元素比待查找的元素小，就说明“如果待查找的元素存在，一定位于序列的后半部分”，这样可以把搜索范围缩小到后半部分，然后再次使用这种算法迭代。这种“每次将搜索范围缩小一半”的思想称为折半查找或二分查找（Binary Search）。
二分查找的条件是事先经过排序，且要求所有备查数据都必须加载到内存中进行。
每次变化的都是中间值，这样每次查找都会比上一次少一半的范围，最多只需要比较log(n)+1次，时间复杂度为O(log(n))。使用二分查找就可以省去一半的遍历。
故python实现代码为
def binarysearch(L,number):
start=0
end=len(L)
while start<=end : #边界条件范围缩小到只有一个元素
mid=(start+end)//2 #取中间位置
if L[mid]<number:
start=mid+1
elif L[mid]>number:
end=mid-1
else:
return mid
return -1
函数接受一个有序数组和一个指定查找的元素。如果该元素包含在数组中，这个函数将返回其位置。而我们所要跟踪的就是每次要查找的数组范围——开始时为整个数组。
测试用例
>>>binarysearch([1,2,6,8,12,13],6)
2
>>>binarysearch ([1,2,6,8,12,13],7)
-1
>>>
因为二分查找使用了分治思想，每个子问题的形式和解法都是相同的，因为可以转化为使用递归求解，如
defrecursionBS(L,number,start,end):
if start>end:
return -1
mid=(start+end)//2
if L[mid]==number:
return mid
elif L[mid]>number:
returnrecursionBS(L,number,start,mid-1)
else:
return recursionBS(L,number,mid+1,end)
测试用例
>>>recursionBS([1,2,6,8,12,13],6,0,6)
2
>>> recursionBS([1,2,6,8,12,13],8,0,6)
3
>>>recursionBS([1,2,6,8,12,13],1,0,6)
0
>>>recursionBS([1,2,6,8,12,13],13,0,6)
5
