Boundary Convergence Search Template

In this Template, both pointers converge towards a single index where left == right. left starts at initial_low and right starts at initial_high. The loop runs while left < right, continually narrowing the search space without skipping potential candidate points (right = mid).

Common use cases: Finding optimal values, peak elements, minimum in rotated arrays, or binary search on an answer range.

Basic Template Structure:

Java

int left = initial_low;
int right = initial_high;

while (left < right) {
    int mid = left + (right - left) / 2;
    // code
    right = mid;
    left = mid + 1;
}
return left; // left == right

int left = initial_low;
int right = initial_high;

while (left < right) {
    int mid = left + (right - left) / 2;
    // code
    right = mid;
    left = mid + 1;
}
return left; // left == right

Scenario 1: – Condition satisfied (Mid is a potential answer). If mid satisfies the required condition or predicate, the optimal answer lies at mid or to its left.

Java

int left = initial_low;
int right = initial_high;

while (left < right) {
    int mid = left + (right - left) / 2;
    // code
    if (condition(mid)) {
        right = mid; // Keep mid as a candidate in the left half
    }
}
return left;

int left = initial_low;
int right = initial_high;

while (left < right) {
    int mid = left + (right - left) / 2;
    // code
    if (condition(mid)) {
        right = mid; // Keep mid as a candidate in the left half
    }
}
return left;

Scenario 2: – Condition not satisfied (Mid is invalid). If mid does not satisfy the required condition or predicate, the optimal answer must lie strictly to the right of mid.

Java

int left = initial_low;
int right = initial_high;

while (left < right) {
    int mid = left + (right - left) / 2;
    // code
    if (!condition(mid)) {
        left = mid + 1; // Exclude mid and search right half
    }
}
return left;

int left = initial_low;
int right = initial_high;

while (left < right) {
    int mid = left + (right - left) / 2;
    // code
    if (!condition(mid)) {
        left = mid + 1; // Exclude mid and search right half
    }
}
return left;

Final Template: – combined all the scenarios into a single structure with generic parameters

Java

int left = initial_low;
int right = initial_high;

while (left < right) {
    int mid = left + (right - left) / 2;
    // code
    if (condition(mid)) {
        // Peak/Target is at mid or in left half
        right = mid;
    } else {
        // Peak/Target is strictly in right half
        left = mid + 1;
    }
}
return left; // left == right

int left = initial_low;
int right = initial_high;

while (left < right) {
    int mid = left + (right - left) / 2;
    // code
    if (condition(mid)) {
        // Peak/Target is at mid or in left half
        right = mid;
    } else {
        // Peak/Target is strictly in right half
        left = mid + 1;
    }
}
return left; // left == right