Вычисление середины в бинарном поиске

Простой ответ, дополнение l + u может переполниться и имеет неопределенное поведение на некоторых языках, как описано в сообщение в блоге Joshua Bloch, об ошибке в библиотеке Java для реализации двоичного поиска .

Некоторые читатели не могут понять то, о чем это:

l + (u - l) / 2

Примечание, что в некотором коде, имена переменной отличаются, и это

low + (high - low) / 2

, ответ: скажем, если у Вас есть два числа: 200 и 210, и теперь Вы хотите "среднее число". И скажем, если Вы добавляете какие-либо два числа, и результат больше, чем 255, тогда он может переполниться, и поведение не определено, тогда что можно сделать? Простой путь состоит в том, чтобы только добавить различие между ними, но всего половину из него, к меньшему значению: посмотрите на то, что различие между 200 и 210. Это 10. (Можно считать это "различием" или "длиной" между ними). Таким образом, просто необходимо добавить 10 / 2 = 5 к 200 и добраться 205. Вы не должны добавлять 200 и 210 вместе сначала - и это - то, как мы можем достигнуть вычисления: (u - l) различие. (u - l) / 2 половина из него. Добавьте, что к l и мы имеем l + (u - l) / 2.

Для помещения этого в перспективы истории Robert Sedgewick упомянул, что первый двоичный поиск был упомянут в 1946, и это не было корректно до 1964. Jon Bentley описал в своей книге, Программируя Жемчуг в 1988, что больше, что 90% профессиональных программистов не могли записать это правильно, учитывая несколько часов. Но даже у самого Jon Bentley была та водосливная ошибка в течение 20 лет. Исследование, которое было опубликовано в 1988, показало, что точный код для двоичного поиска был только найден в 5 из 20 учебников. В 2006 Joshua Bloch записал что сообщение в блоге об ошибке о вычислении эти mid значение. Таким образом, потребовалось 60 лет для этого кода, чтобы быть корректным. Но теперь, в следующий раз в собеседовании, не забывают писать это правильно в этом 20 минут.