如果數組未經排序，可以使用哪種搜索技術？

二進制搜索在O（log n）中執行搜索。但是，它只能在數組排序後使用。如果數組未經排序，可以使用哪種搜索技術？

如果數組未經排序，哪種搜索技術最好？

2012-07-18 Vikram

除非你有關於數組排序的一些信息，否則我認爲你不會比'O（n）'做得更好。 – Mysticial 2012-07-18 00:29:16

順序搜索有什麼問題？對於一個未分類的數組，O（n）大概是你能得到的最好的。 – 2012-07-18 00:29:24

問題是，如果數組沒有排序，那麼在消除數組中的可能元素之後，不會獲得任何額外的信息。因此，最壞的情況是你必須檢查每個元素，給你一個'O（n）'運行時間。 – 2012-07-18 00:53:02

如果您只進行一些搜索，那麼基本的線性搜索就是您可以做的最好的搜索。

如果要經常搜索，通常最好進行排序，然後使用二分搜索（或者，如果內容的分佈如果可以預測的話，則是內插搜索）。

2012-07-18 00:30:48

你可以做一個線性搜索。但是線性搜索的問題在於它有性能問題，需要花費很多時間。所以我建議如果可能的話排序數組，然後使用二進制搜索。如果你想要更好的延遲，那麼嘗試插值搜索，這是典型二進制搜索的一個優化版本。

2017-05-04 11:11:52

如果您的數據未排序，您可以使用散列表在O（1）時間訪問您的數據。

2017-05-04 12:05:12

回答