import java.util.*;
import java.lang.*;
 
class Main
{
  int search(int[] array, int number, int start, int end) {
        System.out.println("Method call");
        int half = (end - start) / 2;
 
        if (array[start + half] == number) {
            return array[start + half];
        }
        if (array[start + half] < number) {
            return search(array, number, start + half, end);
        } else {
            return search(array, number, start, end - half);
        }
    }
 
    public static void main(String[] args) {
        int[] array = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 };
        for (int i : array) {
            System.out.println(i);
            new Main().search(array, i, 0, array.length);
        }
    }
}

aW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CgpjbGFzcyBNYWluCnsKICBpbnQgc2VhcmNoKGludFtdIGFycmF5LCBpbnQgbnVtYmVyLCBpbnQgc3RhcnQsIGludCBlbmQpIHsKICAgICAgICBTeXN0ZW0ub3V0LnByaW50bG4oIk1ldGhvZCBjYWxsIik7CiAgICAgICAgaW50IGhhbGYgPSAoZW5kIC0gc3RhcnQpIC8gMjsKCiAgICAgICAgaWYgKGFycmF5W3N0YXJ0ICsgaGFsZl0gPT0gbnVtYmVyKSB7CiAgICAgICAgICAgIHJldHVybiBhcnJheVtzdGFydCArIGhhbGZdOwogICAgICAgIH0KICAgICAgICBpZiAoYXJyYXlbc3RhcnQgKyBoYWxmXSA8IG51bWJlcikgewogICAgICAgICAgICByZXR1cm4gc2VhcmNoKGFycmF5LCBudW1iZXIsIHN0YXJ0ICsgaGFsZiwgZW5kKTsKICAgICAgICB9IGVsc2UgewogICAgICAgICAgICByZXR1cm4gc2VhcmNoKGFycmF5LCBudW1iZXIsIHN0YXJ0LCBlbmQgLSBoYWxmKTsKICAgICAgICB9CiAgICB9CiAgICAKICAgIHB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZ1tdIGFyZ3MpIHsKICAgICAgICBpbnRbXSBhcnJheSA9IG5ldyBpbnRbXSB7IDEsIDIsIDMsIDQsIDUsIDYsIDcsIDgsIDksIDEwLCAxMSwgMTIsIDEzLCAxNCwgMTUsIDE2IH07CiAgICAgICAgZm9yIChpbnQgaSA6IGFycmF5KSB7CiAgICAgICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbihpKTsKICAgICAgICAgICAgbmV3IE1haW4oKS5zZWFyY2goYXJyYXksIGksIDAsIGFycmF5Lmxlbmd0aCk7CiAgICAgICAgfQogICAgfQp9