Binary Search Bug
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.
Comments
Type system?
[Greg Buchholz] June 4, 2006 16:32:47.770
What does that have to do with type systems? From here, the issue appears to be that our "mainstream languages" have choosen to make modular arithmetic the easy-to-use default :-(. Are we saying that it's impossible to create a class in Smalltalk to handle modular arithmetic? Surely, the answer is no. The fixes have nothing to do with working around the type system, they're working around the semantics of math that wraps. All "mainstream languages" have arbitrary precision number libraries that should be used instead. Maybe you'd like the Haskell language where integers are arbirary precision and you get static type checks that are automatically inferred for you (no type declarations and duck typing, yay!).