Сценарий с худшим случаем двоичного поиска - 1 + lg n, но делает ли это худший случай, если элемент находится в отсортированном массиве или элемент отсутствует? Я думаю, что требуется меньше поисков, чтобы решить, что элемент не находится в массиве, или поиск остается неизменным.О сценариях худшего случая в двоичном поиске
Скажите, что вы должны сделать сравнения k в худшем случае, чтобы проверить, элемент находится в массиве. В последнем (kth) сравнении, если ключ не совпадает, элемент явно не находится в массиве. Поэтому вам не нужно делать больше сравнений, если элемент не находится в массиве после сравнения kth.
Следовательно, худший случай должен оставаться неизменным независимо от того, находится ли элемент в сортированном массиве или нет, на k=ceil(log(n)).
Аналогичным образом, в случае линейного поиска предположим, что ключ находится на последнем месте в массиве. Нам понадобятся сравнения n, и если последний элемент массива не соответствует ключу, мы можем заключить, что элемент не находится в массиве. Нам больше не нужны сравнения, и худший случай будет таким же (n), независимо от того, какой элемент присутствует в массиве или нет.
Существует разница, если вы берете средний случай. Но в худшем случае вы явно ищете самую длинную цепочку сравнений. – Henry