查找預先排序的數組中的給定值的索引

今天，我參加了一次採訪，面試官問我如何在預先排序的數組中找到給定值（數字）的索引，如下所示：查找預先排序的數組中的給定值的索引

$preSortedArr=array(23,32,36,41,45,54);

他還表示，使用遞歸是不允許的。

我認爲功能應該是這樣的：

function findIndexByValue($preSortedArray,$value){    
//some codes here  
}

你怎麼想的解決方案，他從我的期待？

編輯：對不起，我忘了補充說，他原本要我寫僞代碼，但我說我不知道。然後我試圖用PHP編寫它，但我認爲他期待着一種獨立於語言的解決方案。

來源

2010-03-16 bobo

既然他說陣列是預先排序的，他可能期待一個二分查找。線性搜索（自數組排序後可能進行優化 - 如果發現較大值，則退出失敗）在示例中的小陣列上當然會非常好。可能更快，如果它很重要。

來源

2010-03-16 13:10:05

我同意史蒂夫在這一個。通常我會說使用array_search，但他正在尋找思想過程而不是php函數。 – 2010-03-16 13:11:40

@John然後面試官或OP使用了一個非常糟糕的例子:) – Gordon 2010-03-16 13:13:24

我想這真的取決於這是否是「你知道PHP嗎？」問題，還是「你知道算法嗎？」題。如果他只是在尋找'array_search'，爲了證明你知道PHP，那麼數組排序的事實是無關緊要的，對遞歸的禁止也是無關緊要的。但實際上，這是類似於這個例子的數組的正確答案。也許他已經爲'array_search'做好了準備，並且有一個後續問題，「如果數組包含一百萬個值呢？」。 – 2010-03-16 13:15:17

$key = array_search("23", $array);

來源

2010-03-16 13:09:23

+1，因爲你比我快11秒 – Gordon 2010-03-16 13:11:27

他很可能在尋找

array_search - 搜索給定值的數組，並返回相應的鍵，如果成功

編輯現在的問題是有點怪給定的數組。除了PHP的本地函數以外，沒有任何意義。另一種方法是使用while，next,key和current，如果您想親自使用。這仍然不能解釋爲什麼面試官指出你可能不使用遞歸。

來源

2010-03-16 13:09:34 Gordon

他可能不是在尋找任何具體的答案。他可能想在選擇實施方式之前，先看看你是如何思考和考慮不同的選擇，並解釋他們的利弊。

來源

2010-03-16 13:13:02

最好的方法是使用Binary search algorithm。最壞情況的複雜度是o（logn）

來源

2010-03-16 13:23:37 user294770

二分搜索可以在沒有遞歸的情況下實現嗎？ – bobo 2010-03-16 13:25:34

@bobo。當然可以。 – 2010-03-16 14:00:06

是的。 Niklaus Wirth在Standard Pascal [6]中記錄了該算法： min：= 1; max：= N; {array size：var A：array [1 ..N]整數} 重複 mid：=（min + max）div 2; if x> A [mid] then min：= mid + 1 else max：= mid-1;直到（A [mid] = x）或（min> max）; – user294770 2010-03-16 14:00:19

查找預先排序的數組中的給定值的索引

回答

相關問題