import java.util.*;
import java.util.function.*;

public class BinarySearch {

	// 000[1]11
	// warning: overflows in lines 1-4
	public static int binarySearchFirstTrueSimple(IntPredicate predicate, int fromInclusive, int toInclusive) {
		int lo = fromInclusive - 1;
		int hi = toInclusive + 1;
		while (hi - lo > 1) {
			int mid = (lo + hi) / 2;
			if (!predicate.test(mid)) {
				lo = mid;
			} else {
				hi = mid;
			}
		}
		return hi;
	}

	// 000[1]11
	// correct binary search
	public static int binarySearchFirstTrue(IntPredicate predicate, int fromInclusive, int toExclusive) {
		int lo = fromInclusive;
		int hi = toExclusive;
		while (lo < hi) {
			// int mid = lo + ((hi - lo) >>> 1);
			int mid = (lo & hi) + ((lo ^ hi) >> 1);
			if (!predicate.test(mid)) {
				lo = mid + 1;
			} else {
				hi = mid;
			}
		}
		return hi;
	}

	public static double binarySearch(DoublePredicate predicate, double lo, double hi) {
		for (int step = 0; step < 1000; step++) {
			double mid = (lo + hi) / 2;
			if (!predicate.test(mid)) {
				lo = mid;
			} else {
				hi = mid;
			}
		}
		return hi;
	}

	// random test
	public static void main(String[] args) {
		Random rnd = new Random(1);
		for (int step = 0; step < 100_000; step++) {
			int n = rnd.nextInt(20);
			boolean[] b = new boolean[n];
			int firstTrue = rnd.nextInt(n + 1);
			Arrays.fill(b, firstTrue, n, true);
			int res1 = binarySearchFirstTrueSimple(i -> b[i], 0, n - 1);
			int res2 = binarySearchFirstTrue(i -> b[i], 0, n);
			if (res1 != firstTrue || res1 != res2)
				throw new RuntimeException();
		}

		System.out.println(Math.sqrt(2) == binarySearch(x -> x * x >= 2, 0, 2));
	}
}