递归二分查找函数查找不存在值时未返回-1问题排查

Hey there! Let's figure out why your recursive binary search is spitting out garbage values instead of the expected -1 when the target isn't in your array. This is a super common gotcha with recursive implementations—let's break down the most likely culprits and how to fix them.

Common Issues & Fixes #

1. Missing the "not found" base case return #

The first big mistake is forgetting to explicitly return -1 when your search interval is exhausted. When low exceeds high, that means you've checked every possible element and the target isn't present. If you skip returning -1 here, the function will fall through and return whatever random value is left on the call stack (that's your garbage value).

2. Failing to return the result of recursive calls #

Even if you have the base case right, you might be making this mistake: calling the recursive function but not passing its result back up the stack. For example, if you write binarySearch(arr, low, mid-1, target) instead of return binarySearch(arr, low, mid-1, target), the current function frame won't pass the lower recursive call's result back to its caller. Again, this leaves you with garbage when the target isn't found.

Example of a Broken Implementation (to avoid) #

int binarySearch(int list[], int low, int high, int target) {
    if (low <= high) {
        int mid = (low + high) / 2;
        if (list[mid] == target) {
            return mid;
        } else if (list[mid] > target) {
            binarySearch(list, low, mid - 1, target); // No return here!
        } else {
            binarySearch(list, mid + 1, high, target); // No return here!
        }
    }
    // No return -1 here!
}

Fixed Recursive Binary Search #

Here's the corrected version that handles missing targets properly:

int binarySearch(int list[], int low, int high, int target) {
    // Base case: target not found in current interval
    if (low > high) {
        return -1;
    }

    // Calculate mid safely to avoid integer overflow
    int mid = low + (high - low) / 2;

    if (list[mid] == target) {
        return mid; // Return index if target is found
    } else if (list[mid] > target) {
        // Recurse on left half, and return the result
        return binarySearch(list, low, mid - 1, target);
    } else {
        // Recurse on right half, and return the result
        return binarySearch(list, mid + 1, high, target);
    }
}

Key Takeaways #

• Always explicitly return -1 when low > high—this is your "target not found" signal.
• Never call the recursive function without returning its result. Every recursive branch needs to pass the result back up the call stack.
• Use low + (high - low)/2 to calculate mid instead of (low + high)/2 to prevent integer overflow (a bonus fix that avoids other potential bugs).

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