A neat article from Joshua Bloch, a Googler who had earlier implemented binary search in java.util.Arrays. His implementation looked like below.
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: }
The error is in line 6. when the value and high and low is large enough to exceed the max value of an int variable, ArrayIndexOutOfBoundsException wud be thrown.
He says "The general lesson that I take away from this bug is humility: It is hard to write even the smallest piece of code correctly, and our whole world runs on big, complex pieces of code."
This incident makes me reassure the realization that man can never be perfect. Man always fails, tumbles and is weak except for the strength he derives from God.
No comments:
Post a Comment