Другие уже ответили на фундаментальный вопрос - вам придется проверять все записи или, по крайней мере, до того момента, когда вы найдете ноль. Это был бы худший случай из 99 сравнений. (Потому что если первые 99 равны единице, то вы уже знаете, что последняя запись должна быть нулевой, поэтому вам не нужно проверять ее)
Возможный недостаток в этих ответах - предположение, что вы можете проверять только одну запись за раз .
В действительности мы, вероятно, использовали бы прямой доступ к памяти для сравнения нескольких целых чисел одновременно. (Например, если ваше «целое число» составляет 32 бита, то процессоры с инструкциями SIMD могут сравнивать 128 битов одновременно, чтобы увидеть, содержит ли какая-либо запись в группе из 4 значений ноль - это сделает ваше сканирование методом грубой силы чуть менее чем в 4 раза быстрее. Очевидно, что чем меньше целое число, тем больше записей вы можете сравнить одновременно).
Но это не оптимальное решение. Если вы можете диктовать хранилище этих значений, тогда вы можете хранить весь «массив» в виде двоичных битов (значения 0/1) всего в 100 битах (проще всего было бы использовать два 64-битных целых числа). (128 бит) и заполнить оставшиеся 28 бит 1), а затем вы можете выполнить «двоичную отбивку», чтобы найти данные.
По сути, "бинарная отбивная" работает, разбивая данные пополам. Одна половина будет иметь все 1, а другая половина будет иметь ноль. Таким образом, одно сравнение позволяет отклонить половину значений одновременно. (Вы можете сделать одно сравнение, потому что половина вашего массива уместится в 64-битную длину, поэтому вы можете просто сравнить его с 0xffffffffffffffff, чтобы увидеть, все ли это единицы). Затем вы повторяете половину, содержащую ноль, снова разбивая ее на две части и определяя, какая половина содержит ноль ... и так далее. Это всегда найдет нулевое значение в 7 сравнениях - намного лучше, чем сравнивать все 100 элементов по отдельности.
Это может быть дополнительно оптимизировано, потому что как только вы достигнете уровня в один или два байта, вы можете просто посмотреть значение байта / слова в предварительно рассчитанной таблице поиска, чтобы сказать вам, какой бит равен нулю. Это приведет к уменьшению алгоритма до 4 сравнений и одного просмотра (в таблице размером 64 КБ) или 5 сравнений и одного просмотра (в таблице размером 256 байт).
Итак, в худшем случае у нас осталось около 5 операций.
Но если бы вы могли диктовать хранение массива, вы могли бы просто "сохранить" массив, записав индекс нулевой записи. Нет необходимости хранить все отдельные значения. Для сохранения состояния потребуется всего 1 байт памяти, и этот байт уже будет содержать ответ, что даст вам стоимость всего одной операции (чтение сохраненного значения).