Skip to content

Instantly share code, notes, and snippets.

@lexich
Created June 28, 2012 18:13
Show Gist options
  • Save lexich/3013004 to your computer and use it in GitHub Desktop.
Save lexich/3013004 to your computer and use it in GitHub Desktop.
Binary search algoritm
/**
* Binary search algoritm
*/
class BSAlgoritm {
/*
* @param c up sorted container
* @param src search value
* @param loop if false - tail recurcive implementatuion else iterate implementation.
* But it doesnt matter which variant need to use.
*/
public static int bsearch(Integer[] c, Integer src, boolean loop) {
if (c.length == 0)
return -1;
else if (c[0] == src)
return 0;
else if (c[c.length - 1] == 0)
return c.length - 1;
else
return internalBSearch(c, src, 0, c.length - 1, loop);
}
private static int internalBSearch(Integer[] c, Integer src, int from, int to, boolean loop) {
for (; ; ) {
int mid = from + (to - from) / 2;
if (to - from == 1) {
return c[from] == src ? from :
c[to] == src ? to :
-1;
}
if (c[mid] == src) {
int index = mid;
while (index >= 0 && c[index] == src)
index--;
return index + 1;
}
if (!loop) {
return c[mid] < src
? internalBSearch(c, src, mid, to, loop)
: internalBSearch(c, src, from, mid, loop);
} else {
if (c[mid] < src) from = mid;
else to = mid;
}
}
}
}
public class BinarySearch {
public static void main(String[] args) {
Boolean b[] = new Boolean[]{true, false};
for (Boolean loop : b) {
test(loop, new Integer[]{}, "1");
test(loop, new Integer[]{1}, "2");
test(loop, new Integer[]{1, 1, 1, 1, 1}, "3");
test(loop, new Integer[]{1, 2, 3, 4, 5}, "4");
test(loop, new Integer[]{1, 1, 2, 2, 3, 3, 4, 4, 5, 5}, "5");
}
}
private static void test(boolean loop, Integer[] a, String name) {
Integer lastResult = null;
int lastIndex = 0;
int fails = 0;
String funcname = loop ? "iterative" : "recursive";
for (int i = 0; i < a.length; ++i) {
int res = BSAlgoritm.bsearch(a, a[i], loop);
if (res == i) {
lastResult = a[i];
lastIndex = i;
} else if (lastIndex != res) {
fails++;
System.err.println("Test fails '" + funcname + ":" + name + "'. search=" + a[i] + " i=" + i + " res=" + res);
}
}
if (fails == 0) {
System.err.println("Test pass '" + funcname + ":" + name + "'");
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment