Binary Search Bug (Counterexample)

Bob claims that the following program always correctly searches for target in a non-decreasing array: it returns any matching index if target is present, and −1 otherwise. Write a program that reads no input: if the algorithm is correct, output CORRECT; otherwise output any valid counterexample array and target. This site follows the complete Java version of the original OCR053; the program to refute is:

int sorted_search(int[] elements, int target) {
    if (elements == null || elements.length <= 0) return -1;
    int left = 0, right = elements.length - 1;
    while (left < right) {
        int middle = (left + right + 1) / 2;
        if (elements[middle] > target) right = middle - 1;
        else left = middle + 1;
    }
    if (elements[right] == target) return right;
    return -1;
}

The judge accepts any valid witness that makes this algorithm produce a wrong result; it does not have to match the public example you see.

输入格式

No input; standard input is empty. Do not read test parameters that do not exist in the problem.

输出格式

If the program is correct, output CORRECT. Otherwise output exactly three lines: the first line is a non-negative integer n; the second line contains exactly n space-separated integers in non-decreasing order; the third line is target. The elements and target must be Java signed 32-bit integers (−2147483648..2147483647), as determined by the original int interface; the original text gives no separate upper limit on the array length, and this site imposes no artificial small length limit, but the total output is bounded by the 64KiB runtime budget. The witness must make the original program return a wrong result; if target appears more than once, returning any matching index is a correct result, so it cannot serve as a counterexample.

样例 1

输入：

输出：

3
1 2 3
2

样例说明

When searching for 2 in the array [1,2,3], middle=1 and elements[1]=2, yet left=2 is executed; after the loop exits, the check reads elements[2]=3 and wrongly returns −1. So these three lines are a valid counterexample, and CORRECT does not hold.