Binary Search

Algorithm Templates

The essence of binary search is not “monotonicity”, but “boundary”. As long as a certain property is found that divides the entire interval into two, the boundary point can be found using binary search.

Template 1

boolean check(int x) {
}

int search(int left, int right) {
    while (left < right) {
        int mid = (left + right) >> 1;
        if (check(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

Template 2

boolean check(int x) {
}

int search(int left, int right) {
    while (left < right) {
        int mid = (left + right + 1) >> 1;
        if (check(mid)) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }
    return left;
}

When doing binary search problems, you can follow the following routine:

1. Write out the loop condition $left < right$;
2. Inside the loop, you might as well write $mid = \lfloor \frac{left + right}{2} \rfloor$ first;
3. According to the specific problem, implement the $check()$ function (sometimes the logic is very simple, you can not define $check$), think about whether to use $right = mid$ (Template $1$) or $left = mid$ (Template $2$);
   • If $right = mid$, then write the else statement $left = mid + 1$, and there is no need to change the calculation of $mid$, that is, keep $mid = \lfloor \frac{left + right}{2} \rfloor$;
   • If $left = mid$, then write the else statement $right = mid - 1$, and add +1 when calculating $mid$, that is, $mid = \lfloor \frac{left + right + 1}{2} \rfloor$;
4. When the loop ends, $left$ equals $right$.

Note that the advantage of these two templates is that they always keep the answer within the binary search interval, and the value corresponding to the end condition of the binary search is exactly at the position of the answer. For the case that may have no solution, just check whether the $left$ or $right$ after the binary search ends satisfies the problem.

Examples

• Find First and Last Position of Element in Sorted Array
• Sqrt(x)
• Find Peak Element
• First Bad Version
• Fixed Point