复杂度 n/2的k次方 >= 1 O(0)~O(k)

首索引加尾索引整除2
li=[1, 4, 5, 78,156, 178,180, 199]
low=0
hight=len(li)-1

def binary_search(li, target, low, hight):
while low <= hight:
mid = (low + hight) // 2
if n < li[mid]:
hight = mid - 1
elif n > lst[mid]:
low = mid + 1
else:
print(mid+1)
break
else:
print("没有这个数")

binary_search(li,156,low,hight)

递归法

def binary_search(li,target,low,hight):

if low>hight:

return False

else:

mid=(low+hight)//2

if target ==li[mid]:

return mid+1

elif target < li[mid]:

return binary_search(li,target,low,mid-1)

else:

return binary_search(li,target,mid+1,hight)

print(binary_search(li,156,low,hight))

递归，是在函数中自身调用自身的一种情况，直到有一个明确的退出条件成立后结束相互调用。递归是一种很容易理解某类问题的方式，但是不是特别高效，因为每次调用自身时，都会在内存中创建一个新的内存空间，当不断循环调用非常多次时，是非常耗内存的。

算法：当数据量很大适宜采用该方法。采用二分法查找时，数据需是排好序的。
基本思想：假设数据是按升序排序的，对于给定值n，从序列的中间位置mid开始比较，
如果当前位置li[n]值等于mid，则查找成功；
若mid小于当前位置值li[n]，则在数列的前半段中查找,li[left,mid-1]；
若mid大于当前位置值li[n]，则在数列的后半段中继续查找arr[mid+1,right]，