今日閱讀2006-06-08

Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken
一開始是一個簡單的binary search

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:     }

如果low+high比int(2^31-1)大的話, 會有bug

作者提供了解決的方法

6:             int mid = low + ((high - low) / 2);

或者

6:             mid = ((unsigned) (low + high)