Python 2.7递归二分查找代码始终返回False问题排查求助

Hey there! Let's figure out why your recursive binary search keeps spitting out False—this is a super common pitfall with recursive implementations, so let's break down the most likely issues:

1. You're Not Returning the Result of Recursive Calls #

This is the #1 mistake people make with recursive binary search. When you call the function recursively in your if/elif branches, you forget to pass that recursive call's result back up the stack. Here's what that broken code might look like:

def binary_search(arr, target):
    if len(arr) == 0:
        return False
    mid = len(arr) // 2
    if arr[mid] == target:
        return True
    elif arr[mid] > target:
        binary_search(arr[:mid], target)  # Oops! No return here
    else:
        binary_search(arr[mid+1:], target)  # Same mistake here
    return False  # This line always runs eventually

Even if the recursive call finds your target and returns True, that result never makes it back to the original function call. Instead, the code falls through to the final return False, making it look like the target was never found.

2. Your Input Array Isn't Sorted #

Binary search only works on sorted arrays! If your array is out of order, the algorithm has no logical way to narrow down where the target might be. Double-check that your arr is sorted in ascending order (or adjust the comparison logic if you're working with a descending-sorted array).

3. Boundary Condition Off-by-One Errors #

Small mistakes in how you slice the array or calculate the midpoint can cause the target to be missed entirely. For example:

• Using arr[mid:] instead of arr[mid+1:] when the target is larger than arr[mid] will make you recheck the midpoint repeatedly, leading to infinite recursion (or eventually hitting an empty array and returning False).
• Miscalculating mid (though in Python 2.7, len(arr) // 2 works correctly for integer division).

Fixed Code Examples #

Option 1: Slice-Based (Simpler, Less Efficient) #

Here's the corrected version with proper return statements for recursive calls:

def binary_search(arr, target):
    if not arr:
        return False
    mid = len(arr) // 2
    if arr[mid] == target:
        return True
    elif arr[mid] > target:
        return binary_search(arr[:mid], target)  # Pass recursive result up
    else:
        return binary_search(arr[mid+1:], target)  # Pass recursive result up

Option 2: Index-Based (More Efficient) #

For larger arrays, slicing creates new subarrays which wastes memory. Using left/right indexes avoids this overhead:

def binary_search(arr, target, left=0, right=None):
    if right is None:
        right = len(arr) - 1
    # Base case: target not found
    if left > right:
        return False
    mid = (left + right) // 2
    if arr[mid] == target:
        return True
    elif arr[mid] > target:
        # Search left half
        return binary_search(arr, target, left, mid - 1)
    else:
        # Search right half
        return binary_search(arr, target, mid + 1, right)

Quick Checks to Try #

1. First, verify that you're returning the recursive calls (this fixes 90% of cases like this).
2. Test with a small, sorted array like [1,3,5,7,9] and target 5 to confirm the basic logic works.
3. If using the index-based version, make sure your initial right value is len(arr)-1 (not len(arr)—that would cause an out-of-bounds error).

内容的提问来源于stack exchange，提问作者ItsDembo