Binary search in Java
Find a key in a sorted array. Compare the key with the middle item, and keep only the half that can hold the key.
- File
BinarySearch.java, 40 lines- Level
- Native tests
- fail in this build
- Toolchain
- JDK 25, JUnit 5
- Test framework
- JUnit 5
- Run the tests
javac and the JUnit console launcher
// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/binary-search/. The authors are listed in prov/2B7QDX.jsonl.
/** Binary search in a sorted array. */
public final class BinarySearch {
private BinarySearch() {}
/** Returns an index i with a[i] == x, or -1 when x is not in a. The array must be sorted. */
public static int search(long[] a, long x) {
int lo = 0, hi = a.length; // @line L1
while (lo < hi) { // @line L2
int mid = lo + (hi - lo) / 2; // @line L3
if (a[mid] < x) { // @line L4
lo = mid + 1; // @line L5
} else if (a[mid] > x) { // @line L6
hi = mid; // @line L7
} else {
return mid; // @line L8
}
}
return -1; // @line L9
}
/** The same search for any type with a natural order. */
public static <T extends Comparable<? super T>> int search(T[] a, T x) {
int lo = 0, hi = a.length;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
int c = a[mid].compareTo(x);
if (c < 0) {
lo = mid + 1;
} else if (c > 0) {
hi = mid;
} else {
return mid;
}
}
return -1;
}
}
BinarySearchTest.java 43 lines
// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/binary-search/. The authors are listed in prov/2B7QDX.jsonl.
import static org.junit.jupiter.api.Assertions.assertEquals;
import java.util.Arrays;
import java.util.Random;
import org.junit.jupiter.api.Test;
class BinarySearchTest {
@Test
void examples() {
long[] a = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
assertEquals(5, BinarySearch.search(a, 23));
assertEquals(0, BinarySearch.search(a, 2));
assertEquals(9, BinarySearch.search(a, 91));
assertEquals(-1, BinarySearch.search(a, 30));
assertEquals(-1, BinarySearch.search(a, 1));
assertEquals(-1, BinarySearch.search(a, 100));
}
@Test
void edges() {
assertEquals(-1, BinarySearch.search(new long[0], 1));
assertEquals(0, BinarySearch.search(new long[] {7}, 7));
assertEquals(1, BinarySearch.search(new String[] {"ant", "bee", "cat"}, "bee"));
}
@Test
void randomAgainstLinearScan() {
Random rng = new Random(2150);
for (int t = 0; t < 2000; t++) {
long[] a = new long[rng.nextInt(31)];
for (int i = 0; i < a.length; i++) a[i] = rng.nextInt(41) - 20;
Arrays.sort(a);
long x = rng.nextInt(51) - 25;
int got = BinarySearch.search(a, x);
boolean found = Arrays.stream(a).anyMatch(v -> v == x);
if (found) assertEquals(x, a[got]);
else assertEquals(-1, got);
}
}
}
What the next level needs
- the native tests fail
- I1 needs the shared cases of the contract and the JSON adapter (09.2), which are M0 work