бьешь в центр списка, понимаешь выше надо искать или ниже, бьешь в середину ...
второй вариант - ветвление бинарное
третий вариант - в лоб решать. Учитывая вероятность попадания в партию последовательных ID проверку проводить с младшего байта. В общем случае не потребуется проверять все 8 байт для того что-бы сделать вывод, что ключ не подходит.