C++二分查找函数无法返回目标元素索引问题求助

Hey there! Let's work through why your binary search isn't returning the correct index. There are two key issues in your implementation that are causing the problem:

1. Incorrect Initial Value for h (High Bound) #

• You initialized h = arr.length, but array indices in C++ start at 0. For an array with length = 7, the last valid index is 6. Setting h to 7 means you'll end up accessing arr.A[7] at some point, which is out of bounds—this leads to undefined behavior and incorrect comparisons.
• Fix: Change h = arr.length to h = arr.length - 1.

2. Reversed Search Direction Logic #

• Your conditional checks for adjusting the search bounds are backwards:
  • When arr.A[mid] < element, the target is in the right half of the current range, so you should update l = mid + 1 (move the left bound up). But you're setting h = mid -1, which discards the entire right half where the target lives.
  • When arr.A[mid] > element, the target is in the left half, so you should update h = mid -1 (move the right bound down). Your code does the opposite here, setting l = mid +1 and discarding the left half.
• Fix: Swap the logic for adjusting l and h in the else-if blocks.

Corrected Binary Search Function #

int binarySearch(struct array arr, int element) {
    int l, h;
    l = 0;
    h = arr.length - 1; // Fixed high bound
    while (l <= h) { // Using while loop is more idiomatic for binary search than for loop here
        int mid = l + (h - l) / 2; // This avoids potential integer overflow compared to (l+h)/2
        if (arr.A[mid] == element) return mid;
        else if (arr.A[mid] < element) 
            l = mid + 1; // Target is in right half, move left bound up
        else 
            h = mid - 1; // Target is in left half, move right bound down
    }
    return -1;
}

Bonus: Avoid Integer Overflow #

I also changed how mid is calculated to l + (h - l)/2 instead of (l+h)/2. When l and h are large integers, adding them could overflow their int range—this alternative formula is safer and gives the same result.

Testing the Fixed Code #

When you run the corrected code and search for 6, it will return 5 (the correct index of 6 in your array {1,2,3,4,5,6,7}).

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