Статическая типизация - как это мило...
От: Andrei N.Sobchuck Украина www.smalltalk.ru
Дата: 15.06.06 11:55
Оценка: 89 (11) -3
Большинство реализаций бинарного поиска и сортировки слиянием — с ошибкой (by Joshua Bloch):

Я был шокирован, узнав, что программа бинарного поиска, правильность которой доказал 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;

/.../

http://www.smalltalk.ru | << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Я ненавижу Hibernate
Автор: Andrei N.Sobchuck
Дата: 08.01.08
!
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.