我最近学习了二进制搜索。...我对o（log n）的时间复杂性给我留下了深刻的印象，但是我有疑问，对于获得排序的数组i必须采用排序的操作，即最小o（nlogn）复杂性。
如果您的列表未排序（或不能保证要对其进行排序），则线性搜索是要解决的方法。在排序时，线性搜索为O（n）是O（nlog n），这更糟。甚至检查列表是否排序的是o（n）。
如果您只想搜索一次列表，则可以通过线性搜索更好。如果您要搜索几次，则可能会从首先对列表进行排序中受益。为了找出最适合您的特定情况，您必须分析问题。
这个想法是您一次对列表进行排序，并保留结果。随后的搜索是O（log n）。因此，您在许多搜索中的复杂性是(n log n) + S*log(n)，其中S是您进行的搜索数量。如果您不排序数组，则多次搜索为O(S*n)。