查找大於給定數字的最小數字（訪談）

最近我被給了一個面試問題，說你有一個有序的數字列表（元素的數量可能相當大，約爲100000），你會發現大於給定數字的最小數字表示在O（log n）時間內做到這一點的方法......我的第一個猜測是使用像面試官說的yes的數據結構之類的樹，但是他們在建造這些樹木時有一些開銷我可以建議另一種方法？我明顯的答案是使用數組進行二分搜索，雖然想知道這是否會工作，或者有其他的？查找大於給定數字的最小數字（訪談）

來源

2013-03-30 user1950055

[二進制搜索]（http://en.wikipedia.org/wiki/Binary_search_algorithm） –

是的，他們問你是否知道二分查找。 – zch

我認爲二進制搜索是他們想要聽到的。另一方面，如果不知道這個清單是如何組織的，那麼真的不可能提供正確的建議。它可能是一個鏈表。非常有序，但顯然沒有隨機訪問成員。在這種情況下，不會比O（n）更快。 – mikyra

它取決於您正在使用的列表的類型。

如果它沒有索引列表，那麼O（logN）將不可能沒有任何重組。

所以如果它是一個索引列表。

您可以按分割搜索。

比較所述目標與[N/2]

如果A [N/2]小於目標..搜索空間減小。從開始[N/2 + 1] .. A [N-1]

用同樣的方法遞歸算法中，直到找到一對，使得[I] <目標< A [1 + 1]

這將是結束和[i + 1]是你的答案..！

來源

2013-03-30 23:09:20 MissingNumber

你的方法和排序+ OP提出的二分查找有什麼區別？ – angelatlarge

是二進制搜索是我所建議的，但是想知道是否還有其他二進制搜索？ – user1950055

二進制搜索查找任何確切的數字。這是二進制搜索的相同方法，但不僅僅是找到確切的數字。 – MissingNumber

查找大於給定數字的最小數字（訪談）

回答

相關問題