二分法查找
概述
二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好。
其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；
否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。
重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
算法复杂度
二分查找的基本思想是将n个元素分成大致相等的两部分，取a[n/2]与x做比较;
如果x=a[n/2],则找到x,算法中止;
如果x<a[n/2],则只要在数组a的左半部分继续搜索x;
如果x>a[n/2],则只要在数组a的右半部搜索x.
时间复杂度无非就是while循环的次数！
代码示例
# 二分查找算法 # seq 待查序列 # query 要查找的目标 def binary_search(seq, query): # start为起始索引 # end 为结束索引 start, end = 0, len(seq) - 1 while start <= end: mid = start + (end - start) // 2 # // 整除 val = seq[mid] if val == query: # 在seq中找到目标query # 返回对应的索引值 return mid elif val < query: # 目标值大于中间值 # 说明目标值在mid - end之间 start = mid + 1 else: # 目标值小于于中间值 # 说明目标值在start - mid之间 end = mid - 1 # 目标值不存在于seq中，返回None return None if __name__ == "__main__": print("二分查找示例") print("二分查找只适合有序的序列") seq = [1, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 8, 10, 13, 15] print(seq) print("---------二分查找--------") print("找到：", 5, " 索引是： ", binary_search(seq, 5)) print("---------二分查找--------") print("找到：", 4, " 索引是： ", binary_search(seq, 4)) print("---------二分查找--------") print("找到：", 13, " 索引是： ", binary_search(seq, 13)) print("---------二分查找--------") print("找到：", 1, " 索引是： ", binary_search(seq, 1)) print("---------二分查找--------") print("找到：", 25, " 索引是： ", binary_search(seq, 25))
小结
大家可以尝试下如果对乱序序列进行查找会有什么情况出现。
从上文中，我们了解了二分查找基本实现原理和具体的实现算法。
但大家有没有发现，如果目标查找值，如果在查找序列中存在多个，则查找返回的索引值，会有所变化。
那下面我们试着利用二分查找实现以下功能：
-
查找目标值在序列中第一次出现时的索引
-
查找目标值在序列中最后一次出现时的索引
例如，有序列如下：
seq = [1, 2, 3, 4, 5, 5, 5, 5, 6, 7, 8]我们查找目标值： 5
-
第一次出现在索引为：4 的位置
-
最后一次出现在索引为：7 的位置
下面我们对二分查找算法进行策略改造升级为：
# 用于实现二分查找第一次出现的算法
first_binary_search(seq, query)
# 用于实现二分查找最后一次出现的算法
last__binary_search(seq, query)代码实现
first优先策略算法实现
# first二分查找算法 # seq 待查序列 # query 要查找的目标 def first_binary_search(seq, query): # start为起始索引 # end 为结束索引 start, end = 0, len(seq) - 1 while start <= end: mid = start + (end - start) // 2 # // 整除 if (mid == 0 and seq[mid] == query) or (seq[mid] == query and seq[mid - 1] < query): # 这是实现first的最关键判断 # 在seq中找到目标query第一次出现的位置 # 返回对应的索引值 return mid elif seq[mid] < query: # 目标值大于中间值 # 说明目标值在mid - end之间 start = mid + 1 else: # 目标值小于于中间值 # 说明目标值在start - mid之间 end = mid - 1 # 目标值不存在于seq中，返回None return None if __name__ == "__main__": print("二分查找first示例") print("二分查找只适合有序的序列") seq = [1, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 8, 10, 13, 15] # 返回7 print("5第一次出现的索引位置为： ", first_binary_search(seq, 5)) # 返回13 print("7第一次出现的索引位置为： ", first_binary_search(seq, 7)) # 返回15 print("8第一次出现的索引位置为： ", first_binary_search(seq, 8))
last优先策略算法实现
# last二分查找算法 # seq 待查序列 # query 要查找的目标 def last_binary_search(seq, query): # start为起始索引 # end 为结束索引 start, end = 0, len(seq) - 1 while start <= end: mid = start + (end - start) // 2 # // 整除 if (seq[mid] == query and mid == len(seq) - 1) or (seq[mid] == query and seq[mid + 1] > query): # 这是实现last的最关键判断 # 在seq中找到目标query第一次出现的位置 # 返回对应的索引值 return mid elif seq[mid] < query: # 目标值大于中间值 # 说明目标值在mid - end之间 start = mid + 1 else: # 目标值小于于中间值 # 说明目标值在start - mid之间 end = mid - 1 # 目标值不存在于seq中，返回None return None if __name__ == "__main__": print("二分查找last示例") print("二分查找只适合有序的序列") seq = [1, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 8, 10, 13, 15] # 返回9 print("5最后一次出现的索引位置为： ", last_binary_search(seq, 5)) # 返回14 print("7最后一次出现的索引位置为： ", last_binary_search(seq, 7)) # 返回15 print("8最后一次出现的索引位置为： ", last_binary_search(seq, 8))
代码示例2
版本一：
l = [1,2,4,5,6,7,8,9,10,11,12,13,14,15,16,355,3375,3653,6655] def binary_search(l,num): print(l) if len(l)>1: mid_index = len(l)//2 if num >l[mid_index]: #in the right l = l[mid_index:] binary_search(l,num) elif num < l[mid_index]: #in the left l = l[:mid_index] binary_search(l,num) else: print('find it ') else: if l[0]==num: print('find it') else: print('not exist') return binary_search(l,65)
运行结果：
[1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 355, 3375, 3653, 6655] [11, 12, 13, 14, 15, 16, 355, 3375, 3653, 6655] [16, 355, 3375, 3653, 6655] [16, 355] [16] not exist
版本二：
n = [1,2,4,5,6,7,8,9,10,11,12,13,14,15,16,355,3375,3653,6655] def binary_search(n,num): print(n) if len(n)==1: if n[0]==num: print('find it') else: print('not exists') return mid_index = len(n)//2 mid_value = n[mid_index] if num == mid_value: print('find it') return if num > mid_value: n = n[mid_index:] if num < mid_value: n = n[:mid_index] binary_search(n,num) binary_search(n,355)
运行结果：
[1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 355, 3375, 3653, 6655] [11, 12, 13, 14, 15, 16, 355, 3375, 3653, 6655] [16, 355, 3375, 3653, 6655] [16, 355] find it