Да, вы можете сказать, что сложность времени выполнения наилучшего случая для алгоритма двоичного поиска - это Theta (1), а сложность времени выполнения худшего случая для алгоритма двоичного поиска - это Theta (log n). Чтобы объяснить это, мы углубимся в определения Big O, Big Omega и Big Theta, которые являются асимптотическими c нотациями для описания времени и пространственной сложности алгоритмов.
При обращении к лучшим / Наихудшее время выполнения алгоритма, вы обычно ссылаетесь на одну функцию. Нотация Big O используется для описания алгоритмов по времени их верхней границы, а нотация Big Omega используется для описания алгоритмов по времени их нижней границы.
Проще говоря, Big O означает, что алгоритм не может и не будет работать медленнее, чем функция, ограниченная в Big O. Big Omega означает, что алгоритм не может и не будет работать быстрее, чем ограниченная функция в пределах большой омеги. Чтобы использовать нотацию Big Theta для описания сложности времени выполнения алгоритма, время выполнения алгоритма должно включать в себя одну и ту же функцию для обозначений Big O и Big Omega.
В случае бинарного поиска: описывается лучший случай, когда первым элементом в алгоритме поиска является элемент или элемент, который вы ищете. Это означает, что независимо от того, что произойдет, алгоритм должен будет смотреть только на один и тот же элемент. Следовательно, эта ситуация может быть описана как имеющая время работы O (1) и Omega (1). Поскольку эти две функции одинаковы, можно сказать, что наилучшим временем выполнения двоичного алгоритма поиска является Theta (1).
Описан наихудший случай двоичного поиска, когда каждый элемент нужно посмотреть, и последний проверенный элемент - это элемент, который ищет поиск, или элемент просто не существует в структуре данных. Поскольку бинарный поиск использует концепцию «разделяй и властвуй» для просмотра каждого элемента, тривиально, что время выполнения алгоритма в его наихудшем случае должно быть ограничено некоторой формой (log n). В частности, мы можем сказать, что он будет иметь время выполнения как O (log n), так и Theta (log n), потому что алгоритм не сможет работать быстрее или медленнее из-за установленного количества элементов, которые он должен смотреть в. В этом случае две функции одинаковы, поэтому правильно сказать, что наихудшее время работы двоичного алгоритма поиска - Theta (1).