Python中的二进制搜索实现

Question

我正在尝试使用二分查找来实现解决方案。我有

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 

，但是当我试图实现这一点，我得到这样的错误号的列表：索引超出范围。请帮助确定问题。

Answer 1

有几件事。

1. 您的命名不一致。此外，不要使用list作为变量名称，而是隐藏全局内置。

2. 停止条件是while low <= high。这个很重要。

3. 当您找到一个值时，您不会中断。这将导致无限递归。

---

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 

Answer 2

UPDATEhigh = len(lst) - 1每下面的评论。

---

三个问题：

1. 您使用l2s代替list（参数的实际名称）。
2. 您的while条件应该是low <= high而不是low < high。
3. 您应该在找到该值时返回索引，如果找不到则返回None（或者可能是-1？）。

一对夫妇的其他小的变化我做：

• 这是一个坏主意，隐藏内置list。我将参数重命名为lst，在这种情况下，这在Python中通常使用。
• mid = (low + high) // 2是找到中点的更简单形式。
• Python约定是使用snake_case，而不是camelCase，所以我重命名了这个函数。

固定码：

def binary_search(lst, sval): 
    low = 0 
    high = len(lst) - 1 

    while low <= high: 
     mid = (low + high) // 2 

     if lst[mid] == sval: 
      return mid 
     elif lst[mid] > sval: 
      high = mid - 1 
     else: 
      low = mid + 1 

    return None 

print(binary_search([1, 2, 3, 4, 6], 2)) # 1