在 Python 中创建一个简单的二进制搜索函数

Question

基于一道LeetCode题解，我正在练习制作二分查找算法。我在下面写了这个，混合使用了 LeetCode 解决方案中的代码和新代码。在运行上，它无法按预期打印最终字符串。

编辑：我忘了提到，除了不打印到控制台外，代码在预期的时间内执行得很好，没有错误。

binary_search_func 使用与 LeetCode 问题几乎完全相同的代码，但增加了计数器。

我最好的猜测是 While 循环条件有问题，尽管当我将它更改为 While True 时，'break' 作为 guess(mid) == 0 的 if 语句的一部分，它没有根本没用。

代码如下：

target = int(input("Enter the target value.\n"))
maximum = int(input("Now, enter maximum value, for range of search.\n"))

def binary_search_func(n):
    """Search for a specific value within a range of 1 to n."""    

    low = 1
    high = n
    count = 1
    
    while low <= high:
        mid = int(low + (high - low) / 2)

        if guess(mid) == 0:
            print(f"Found {mid}, taking {count} turns.")
        
        elif guess(mid) == 1:
            low = mid + 1
            
        elif guess(mid) == -1:
            high = mid - 1
        
        count += 1


def guess(num):
    """Return value, depending upon whether guessed val == target val."""

    if num == target:
        return 0

    elif num > target:
        return 1

    elif num < target:
        return -1

binary_search_func(maximum)

Answer 1

试试这个代码：

# Returns index of x in arr if present, else -1 
def binary_search(arr, low, high, x): 
  
    # Check base case 
    if high >= low: 
  
        mid = (high + low) // 2
  
        # If element is present at the middle itself 
        if arr[mid] == x: 
            return mid 
  
        # If element is smaller than mid, then it can only 
        # be present in left subarray 
        elif arr[mid] > x: 
            return binary_search(arr, low, mid - 1, x) 
  
        # Else the element can only be present in right subarray 
        else: 
            return binary_search(arr, mid + 1, high, x) 
  
    else: 
        # Element is not present in the array 
        return -1
  
# Test array 
arr = [ 2, 3, 4, 10, 40 ] 
x = 10
  
# Function call 
result = binary_search(arr, 0, len(arr)-1, x) 
  
if result != -1: 
    print("Element is present at index", str(result)) 
else: 
    print("Element is not present in array")

Answer 2

您将进入二进制范围的错误一侧。 guess returns -1 时应该看右边，反之

其次，当你有匹配的时候，你应该退出循环，否则会无限循环。

if guess(mid) == 0:
    print(f"Found {mid}, taking {count} turns.")
    break  # add this
elif guess(mid) == -1:  # corrected
    low = mid + 1
elif guess(mid) == 1:   # corrected
    high = mid - 1

实际上，您不需要 if 的最后一个块是 elif，因为这是剩下的唯一可能性。它可以只是一个 else.

在 Python 中创建一个简单的二进制搜索函数

Creating a simple binary search function in Python

python

binary-search