Python中的二进制搜索实现 [英] Binary Search implementation in Python

问题描述

我正在尝试使用二进制搜索实现解决方案.我有一个数字列表

I am trying to implement a solution using binary search. I have a list of numbers

list = [1, 2, 3, 4, 6]
value to be searched = 2

我写了这样的东西

def searchBinary(list, sval):
    low = 0
    high = len(list)

    while low < high:
        mid = low + math.floor((high - low) / 2)

        if list[mid] == sval:
            print("found : ", sval)
        elif l2s[mid] > sval:
            high = mid - 1
        else:
            low = mid + 1

但是当我尝试实现这一点时，出现了类似错误:索引超出范围.请帮助确定问题.

but when I am trying to implement this, I am getting an error like: index out of range. Please help in identifying the issue.

推荐答案

一些事情.

1. 您的命名不一致.另外，请勿将list用作变量名，否则会掩盖全局内置变量.

1. Your naming is inconsistent. Also, do not use list as a variable name, you're shadowing the global builtin.

停止条件为while low <= high.这个很重要.

The stopping condition is while low <= high. This is important.

找到值时不会中断.这将导致无限递归.

You do not break when you find a value. This will result in infinite recursion.

---

def searchBinary(l2s, sval): # do not use 'list' as a variable
    low = 0
    high = len(l2s) 

    while low <= high: # this is the main issue. As long as low is not greater than high, the while loop must run
        mid = (high + low) // 2

        if l2s[mid] == sval:
            print("found : ", sval)
            return
        elif l2s[mid] > sval:
            high = mid - 1
        else:
            low = mid + 1

现在，

list_ = [1, 2, 3, 4, 6]
searchBinary(list_, 2)

输出:

found :  2

这篇关于Python中的二进制搜索实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！