sorting - 对未排序的数组进行排序和二进制搜索 n 次或线性搜索未排序的数组 n 次更好？

Question

我想搜索一个未排序的数组，n 次查找小于给定数量的特定值集，而不是数组元素。那么排序然后进行n次二进制搜索还是在未排序的数组中进行线性搜索更好

Answer 1

如果 n 很小，则在无序数组中搜索具有性能优势：

n = 小

Sorting: Zero time (0)
Searching: Linear time (n)    

Sum: Linear time (n)

n = 大

Sorting: Zero time (0)
Searching: Quadratic time (n²) 

Sum: Quadratic time (n²)

如果 n 较大，则更好地对数组进行排序，然后进行二进制搜索：

n = 小

Sorting: Linearithmic time (n log n)
Searching: Logarithmic time (log n)

Sum: Linearithmic time (n log n)

n = 大

Sorting: Linearitmnic time (n log n)
Searching: Linearithmic time (n log n)

Sum: Linearithmic time (n log n)

我不能告诉你临界点在哪里，但你可以做一些实验。;)