python算法题练习---二分法
导言：记录下学习的算法题，写练多，脑子才能转的快！
今日算法题：二分法查找
说下我对于二分法查找的理解：【和猜数字游戏差不多】
要在一个有序数列中找到一个与对应给定数字。
1、找到有序数列中最中间的数字
2、若中间值大于给定值，则在左边数列重新二分查找
3、若中间值小于给定值，则在右边数列重新二分查找
4、若都不存在，则返回‘没有对应的匹配值’
【索引思想】
1、设置最大和最小索引，找到中间索引值
2、若中间索引值大于给定值，则中间索引位置前一位变为最大索引位置，最小索引位为0；
3、若中间索引值小于给定值，则中间索引位置下一位变为最小索引位置，最大索引位不变；
4、若都不存在，则返回‘没有对应的匹配值’
错误的代码，没有考虑数组的改变会导致索引的位置变化
if len(arr) >= 1:
mid = int((len(arr)-1)/2)
if arr[mid] == number:
return mid
elif arr[mid] < number:
return searchBinary(arr[mid+1::], number)
elif arr[mid] > number:
return searchBinary(arr[::mid-1], number)
else:
print('没有匹配的值')于是，我考虑了索引位置的改变
def searchBinary(arr, number):
low = 0
height = len(arr)-1
while low <= height:
mid = int((low+height)/2)
if arr[mid] > number:
height = mid-1
elif arr[mid] < number:
low = mid+1
else:
return mid
return '没有匹配值'但是又想要用递归来实现
def searchBinary(arr, number,low,height):
if low <= height:
mid = int((low+height)/2)
if arr[mid] == number:
return mid
elif arr[mid] >= number:
return searchBinary(arr, number, 0, mid-1)
else:
return searchBinary(arr, number, mid+1, height)
else:
return '没有匹配'本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2020-07-30，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
