Двоичный (бинарный) поиск C#-like
В работе над проектом одной из игр, мне пришлось работать с алгоритмами упаковки прямоугольников (задача о ранце) для составления атласа спрайта графики.
В одном из алгоритмов (реализация которого была написана на C#) использовался двоичный поиск. Стандартными средствами AS3 было не обойтись, к тому же бинарный поиск в C# в случае отсутствия искомого элемента возвращает отрицательное число, являющееся побитовым дополнением индекса наиболее близкого к искомому элементу (наиболее близкое всегда больше искомого), а если и такой элемент не найден, то возвращается отрицательное число, являющееся побитовым дополнением длины массива.
Двоичный (бинарный) поиск (также известен как метод деления пополам и дихотомия) — классический алгоритм поиска элемента в отсортированном массиве (векторе), использующий дробление массива на половины. Используется в информатике, вычислительной математике и математическом программировании.
Источник: Двоичный (бинарный) поиск
Read More…
