二分查找

二分查找:

 每次能够排除掉一半的数据. 查找的效率非常高. 但是局限性比较大.  要求: 查找的序列必须是有序序列

# 判断n是否在lst中出现. 如果出现请返回n所在的位置
# 二分查找---非递归算法

def bin_search(li, val):
　　low = 0
　　high = len(li)-1
　　while low <= high: # 只要候选区不空,继续循环
　　　　mid = (low + high) // 2
　　　　if li[mid] == val:
　　　　　　return mid
       elif li[mid] < val:
　　　　　　low = mid + 1
　　　　else: # li[mid] > val
　　　　　　high = mid - 1
　　return -1

普通递归版本二分法
def binary_search(n, left, right):
 if left <= right:
 middle = (left+right) // 2
 if n < lst[middle]:
right = middle - 1
 elif n > lst[middle]:
 left = middle + 1
 else:
 return middle
 return binary_search(n, left, right) # 这个return必须要加. 否则接收
到的永远是None.
 else:
 return -1
print(binary_search(567, 0, len(lst)-1))

# 另类⼆分法, 很难计算位置.
def binary_search(ls, target):
 left = 0
 right = len(ls) - 1
 if left > right:
 print("不在这⾥")
 middle = (left + right) // 2
 if target < ls[middle]:
 return binary_search(ls[:middle], target)
 elif target > ls[middle]:
 return binary_search(ls[middle+1:], target)
 else:
 print("在这⾥")
binary_search(lst, 567)

时间复杂度最低, 空间复杂度最低

lst1 = [5,6,7,8]
lst2 = [0,0,0,0,0,1,1,1,1]
for el in lst1:
    lst2[el] = 1

lst2[4] == 1   # o(1)