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));
	}
}

@@ -121,16 +121,61 @@
 nes 1-4%0A
+%09// invariant: f%5Blo%5D == false, f%5Bhi%5D == true%0A
 %09public 
@@ -222,33 +222,25 @@
 ntPredicate 
-predicate
+f
 , int fromIn
@@ -381,33 +381,25 @@
  2;%0A%09%09%09if (!
-predicate
+f
 .test(mid)) 
@@ -559,25 +559,17 @@
 edicate 
-predicate
+f
 , int fr
@@ -757,33 +757,25 @@
 1);%0A%09%09%09if (!
-predicate
+f
 .test(mid)) 
@@ -897,25 +897,17 @@
 edicate 
-predicate
+f
 , double
@@ -1011,17 +1011,9 @@
 f (!
-predicate
+f
 .tes

Update BinarySearch.java