Сортировка незарегистрированного массива с использованием двоичного поиска?

Нет, это не поможет улучшить временную сложность. Узким местом будет сортировка, которая (без каких-либо доступных предположений о данных) имеет временную сложность O(nlogn), что хуже, чем линейная временная сложность, которую вы получаете при выполнении линейного поиска в несортированном массиве.

Даже если у вас есть данные, для которых подходит сортировка по основанию, и вы получаете отсортированный массив с линейной временной сложностью, это все равно не улучшит временную сложность, которую вы уже имели с наивным поиском.

Без какой-либо дополнительной информации вы не сможете добиться большего, чем линейная временная сложность. Вы можете легко понять это, когда поймете, что любой слот в вашем массиве может содержать искомый элемент. Таким образом, в худшем случае это будет последний слот, который вы просматриваете после проверки всех остальных n-1 слотов в массиве. Следовательно, вы выполнили n операций, что представляет собой линейную временную сложность.

Как вы также спрашивали о сложности пространства: сортировку можно выполнять на месте, поэтому это не повлияет на сложность пространства, если вы все же решите сортировать свои данные.

Если вы сортируете, а затем ищете каждый раз, когда что-то нужно искать, вся операция занимает O (nlogn), что хуже, чем O (n) для линейного поиска.

OTOH, если содержимое списка никогда не меняется (или меняется очень редко), вы можете уйти от сохранения отсортированной копии в начале, а затем запускать все поиски в копии.

Вы можете достичь O (logn) поиска изменяющихся списков, если ваш список реализован как отсортированная структура данных (обычно это двоичное дерево поиска), хотя ваши операции со списками, такие как добавление и удаление в список, становятся O (логин) также. Java TreeSet/TreeMap использует это.