пятница, 30 октября 2009 г.

Старая ошибка в бинарном поиске в Java

Случайно наткнулся на статью Joshua Bloch о любопытной ошибке в реализации бинарного поиска в старой версии Java. Вот ссылка http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html. Суть проблемы в том, что на массивах из очень большого количества элементов(примерно миллиард элементов) данный поиск бы ломался. Причина этого, неочевидна, но проста. А именно при сложении двух чисел типа int можно получить число, больше максимально возможного для int. А, как мы знаем, в бинарном поиске позиция текущего элемента вычисляется, как среднее между двумя числами:

int mid =(low + high) / 2;

Джош переписывает эту строчку кода на:

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

или что лучше по производительности:
int mid = (low + high) >>> 1;

Последняя строка сейчас и используется в Arrays и в Collections. Вот такая забавная история.

Комментариев нет:

Отправить комментарий