This is interesting - the "stock" binary search algorithm fails (for the mainstream statically typed languages):
1: public static int binarySearch(int[] a, int key) {
2: int low = 0;
3: int high = a.length - 1;
4:
5: while (low <= high) {
6: int mid = (low + high) / 2;
7: int midVal = a[mid];
8:
9: if (midVal < key)
10: low = mid + 1;
11: else if (midVal > key)
12: high = mid - 1;
13: else
14: return mid; // key found
15: }
16: return -(low + 1); // key not found.
17: }
Line 6 causes problems if (low + high) overflows the size of an int. This is a non-problem in Smalltalk, of course; you seamlessly get large integers and everything "just works". I found the fixes amusing; they are all ways of coding around the limits of the type system.