如何用二分查找返回姓氏首次出现索引？代码输出索引偏大多1

Hey there! Off-by-one errors are the bane of binary search implementations—let’s figure out why your function’s returning an index that’s always one higher than it should be, especially for cases like searching for "Zulauf".

Common Culprits & Fixes #

Let’s break down the most likely issues and how to fix them:

1. Incorrect Right Bound Initialization
   A super common mistake is setting right to the length of the array instead of array_length - 1. For example:

   // Wrong: right starts at n instead of n-1
   int right = n;
   

   If your loop logic relies on left <= right, this extra index can throw off your final result, leading to a return value that’s one too high. Fix this by initializing right to n - 1.

2. Not Continuing to Search Left After Finding a Match
   Since you need the first occurrence of the surname, you can’t just return the first mid that matches. Instead, you need to keep searching the left half to see if there’s an earlier match, while keeping track of the current valid index. Here’s how to adjust that logic:

   if (arr[mid].last_name == target) {
       result = mid; // Save the current match index
       right = mid - 1; // Keep looking left for earlier occurrences
   }
   

   If your original code returned mid immediately here, you might be catching a later occurrence, but more likely, the off-by-one comes from not handling this leftward search properly.

3. Incorrect Return Value After Loop Termination
   If your loop ends and you return left instead of a pre-saved result, you might be getting the first index after the target (which would be +1 of the correct position). Always track the first valid match during the loop and return that stored value instead of relying on loop variables.

Example Correct Implementation #

Here’s a full example of a binary search function that finds the first occurrence of a surname in a sorted Person struct array:

#include <string>

struct Person {
    std::string last_name;
    // Add other fields as needed
};

int binaryFindFirst(const Person arr[], int n, const std::string& target) {
    int left = 0;
    int right = n - 1;
    int firstIndex = -1; // Default to -1 if not found

    while (left <= right) {
        // Calculate mid safely to avoid integer overflow
        int mid = left + (right - left) / 2;

        if (arr[mid].last_name == target) {
            firstIndex = mid; // Record the current match
            right = mid - 1;  // Keep searching left for earlier matches
        } else if (arr[mid].last_name < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return firstIndex;
}

Quick Checks to Verify #

• Ensure your array is sorted: Binary search only works on sorted data—if your Person array isn’t sorted by last_name, all bets are off.
• Double-check string comparisons: Make sure you’re comparing case correctly (e.g., "Zulauf" vs "zulauf" are different in C++ string comparisons unless you normalize them first).
• Test edge cases: Try searching for the first element, last element, a middle element, and a non-existent surname to confirm the function behaves as expected.

If you’re still seeing issues, feel free to share a snippet of your original code—we can pinpoint exactly where the off-by-one is creeping in!

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