二分查找算法疑问：FFTTTT类字符串的边界查找困惑

Hey there! Let's break down this binary search problem step by step—this pattern is super useful for finding boundaries in sorted sequences like your "FFTTTT" string.

先搞懂找最左侧T的代码逻辑 #

First, let's walk through the code you provided for finding the leftmost T (which maps to the first bad version in the problem context):

public int firstBadVersionLeft(int n) {
    int i = 1;
    int j = n;
    while (i < j) {
        int mid = i + (j - i) / 2;
        if (isBadVersion(mid)) {
            j = mid;
        } else {
            i = mid + 1;
        }
    }
    return i;
}

Here's what each part does:

• Initialization: We start with i=1 and j=n—assuming our sequence is 1-indexed, where F means isBadVersion(mid) returns false, and T means it returns true.
• Loop condition: We run while i < j because once i equals j, we've found our target position.
• Mid calculation: Using i + (j - i)/2 instead of (i + j)/2 avoids integer overflow—critical when working with large values of n (since i + j could exceed the maximum int value in Java).
• Core decision logic:
  • If isBadVersion(mid) is true (we hit a T), that means the leftmost T is either at mid or somewhere to the left. So we move the right pointer j to mid (we can't skip mid because it might be the first T).
  • If it's false (we hit an F), the leftmost T has to be to the right of mid, so we move the left pointer i to mid + 1 (since mid is definitely an F, we don't need to keep it in our search range).
• Final return: When the loop ends, i and j will be pointing to the same position—this is our leftmost T.

如何修改代码找最右侧的F #

Now, if you need to find the rightmost F (the last "good" version), we adjust the binary search logic slightly to target the right boundary instead of the left:

public int lastGoodVersionRight(int n) {
    int i = 1;
    int j = n;
    while (i < j) {
        // Use upper mid to avoid infinite loops
        int mid = i + (j - i + 1) / 2;
        if (!isBadVersion(mid)) {
            // Current is F, so rightmost F is at mid or to the right
            i = mid;
        } else {
            // Current is T, so rightmost F is to the left of mid
            j = mid - 1;
        }
    }
    return i;
}

The key differences here:

• Mid calculation: We use i + (j - i + 1)/2 to get the upper median. If we used the lower median like before, we could hit an infinite loop when i and j are adjacent (e.g., i=2, j=3—lower mid is 2, and if it's an F, i stays 2, looping forever).
• Decision logic:
  • If !isBadVersion(mid) is true (we hit an F), the rightmost F is either at mid or further right, so we move i to mid.
  • If it's false (we hit a T), the rightmost F must be to the left of mid, so we move j to mid - 1.
• Final return: Again, i and j converge to the rightmost F position when the loop ends.

常见误区提醒 #

• Avoid integer overflow: Always use i + (j - i)/2 (or the upper median variant) instead of (i + j)/2 for mid calculations.
• Left vs right boundary mid calculation: Use lower median for left boundaries, upper median for right boundaries to prevent infinite loops.
• Loop condition: Stick with i < j—once i == j, you've found your target, no need to keep looping.

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