二分查找

coolsummer2080

#二分法查找

ls = [34, 64, 67, 72, 73, 82, 83, 85, 87, 88, 90, 91, 96, 98]

print('列表为：', ls)

x = int(input('请输入待查找的数据：'))
low = 0
high = len(ls) - 1

while low < high:
    mid = (low + high) // 2
    if ls[mid] < x:
        low = mid + 1
    elif x < ls[mid]:
        high = mid -1
    else:
        print('找到{}，索引为：{}。'.format(x, mid))
        break
else:
    print('{}不在列表中!'.format(x))

这个算法错在哪里？列表中有的元素查不到。

小甲鱼的铁粉

low = mid + 1
high = mid -1

这里的加减弄反了

#二分法查找

ls = [34, 64, 67, 72, 73, 82, 83, 85, 87, 88, 90, 91, 96, 98]

print('列表为：', ls)

x = int(input('请输入待查找的数据：'))
low = 0
high = len(ls) - 1

while low < high:
    mid = (low + high) // 2
    if ls[mid] < x:
        low = mid - 1
    elif x < ls[mid]:
        high = mid + 1
    else:
        print('找到{}，索引为：{}。'.format(x, mid))
        break
else:
    print('{}不在列表中!'.format(x))

coolsummer2080

小甲鱼的铁粉 发表于 2020-11-27 21:24
这里的加减弄反了

当x大于中间值，查找范围不是应该从原中间点位置的右边一个元素开始么？所以low = mid +1啊。

小甲鱼的铁粉

coolsummer2080 发表于 2020-11-27 21:52
当x大于中间值，查找范围不是应该从原中间点位置的右边一个元素开始么？所以low = mid +1啊。

如果是low = mid + 1   high = mid - 1
while那里改一下，改为：

while low <= high

因为当查找到最后一个元素时，high是等于low的，这个元素可能就是目标元素，但因为while条件没有high=low的情况，就没有进入循环

coolsummer2080

小甲鱼的铁粉 发表于 2020-11-27 22:15
如果是low = mid + 1   high = mid - 1
while那里改一下，改为：

是的。加上等于的情况，错误排除了。谢谢！

小甲鱼的铁粉

coolsummer2080 发表于 2020-11-27 23:41
是的。加上等于的情况，错误排除了。谢谢！

如果问题解决，请设置一个最佳答案