От: | Andrei N.Sobchuck | www.smalltalk.ru | |
Дата: | 15.06.06 11:55 | ||
Оценка: | 89 (11) -3 |
Я был шокирован, узнав, что программа бинарного поиска, правильность которой доказал Bentley и которая позже была проверена в 5-м разделе "Programming Pearls" содержит баг. Когда я покажу вам этот баг вы поймёте почему его не нашли в течении 2-х десятилетий.
/.../
Реализация бинарного поиска, которую я написал для JDK содержит тот же баг. О нём недавно сообщил в SUN, кто-то, подорвавшийся на баге, сидевшем в засаде около 9 лет.
И так, что за баг? Вот стандартный бинарный поиск на Java (то, что я написал для java.util.Arrays):
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: }
Баг в этой строчке:
6: int mid =(low + high) / 2;
/.../