Iterative Binary Search Algorithm
In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. In particular, fractional cascading speeds up binary searches for the same value in multiple arrays. In 1957, William Wesley Peterson published the first method for interpolation search. In 1946, John Mauchly made the first mention of binary search as part of the Moore School lecture, a seminal and foundational college course in computing. In 1962, Hermann Bottenbruch exhibited an ALGOL 60 implementation of binary search that put the comparison for equality at the end, increase the average number of iterations by one, but reduce to one the number of comparisons per iteration.
package Searches;
import java.util.Arrays;
import java.util.Random;
import java.util.stream.Stream;
import static java.lang.String.format;
/**
* Binary search is one of the most popular algorithms
* This class represents iterative version {@link BinarySearch}
* Iterative binary search is likely to have lower constant factors because it doesn't involve the overhead of manipulating the call stack.
* But in java the recursive version can be optimized by the compiler to this version.
* <p>
* Worst-case performance O(log n)
* Best-case performance O(1)
* Average performance O(log n)
* Worst-case space complexity O(1)
*
* @author Gabriele La Greca : https://github.com/thegabriele97
* @author Podshivalov Nikita (https://github.com/nikitap492)
* @see SearchAlgorithm
* @see BinarySearch
*/
public final class IterativeBinarySearch implements SearchAlgorithm {
/**
* This method implements an iterative version of binary search algorithm
*
* @param array a sorted array
* @param key the key to search in array
* @return the index of key in the array or -1 if not found
*/
@Override
public <T extends Comparable<T>> int find(T[] array, T key) {
int l, r, k, cmp;
l = 0;
r = array.length - 1;
while (l <= r) {
k = (l + r) >>> 1;
cmp = key.compareTo(array[k]);
if (cmp == 0) {
return k;
} else if (cmp < 0) {
r = --k;
} else {
l = ++k;
}
}
return -1;
}
//Only a main method for test purpose
public static void main(String[] args) {
Random r = new Random();
int size = 100;
int maxElement = 100000;
Integer[] integers = Stream.generate(() -> r.nextInt(maxElement)).limit(size).sorted().toArray(Integer[]::new);
//the element that should be found
Integer shouldBeFound = integers[r.nextInt(size - 1)];
IterativeBinarySearch search = new IterativeBinarySearch();
int atIndex = search.find(integers, shouldBeFound);
System.out.println(String.format("Should be found: %d. Found %d at index %d. An array length %d"
, shouldBeFound, integers[atIndex], atIndex, size));
int toCheck = Arrays.binarySearch(integers, shouldBeFound);
System.out.println(format("Found by system method at an index: %d. Is equal: %b", toCheck, toCheck == atIndex));
}
}
