30 lines
847 B
Java
30 lines
847 B
Java
public class BinarySearchIterative {
|
|
|
|
public static int binarySearch(int[] nums, int check) {
|
|
int hi = nums.length - 1;
|
|
int lo = 0;
|
|
while (hi >= lo) {
|
|
int guess = (lo + hi) >>> 1; // from OpenJDK
|
|
if (nums[guess] > check) {
|
|
hi = guess - 1;
|
|
} else if (nums[guess] < check) {
|
|
lo = guess + 1;
|
|
} else {
|
|
return guess;
|
|
}
|
|
}
|
|
return -1;
|
|
}
|
|
|
|
public static void main(String[] args) {
|
|
int[] haystack = {1, 5, 6, 7, 8, 11};
|
|
int needle = 5;
|
|
int index = binarySearch(haystack, needle);
|
|
if (index == -1) {
|
|
System.out.println(needle + " is not in the array");
|
|
} else {
|
|
System.out.println(needle + " is at index " + index);
|
|
}
|
|
}
|
|
}
|