查找在未知長度的數組x的位置

-3

給定一個無限陣列（未知陣列長度）和有n個本無限陣列排序整數的元素。 n（排序元素的數量）未知。在logn時間內在這個無限數組中查找整數i的位置。查找在未知長度的數組x的位置

來源

2012-09-20 ealeon

無限數組！= =未知數組長度 – raam86

可能是算法分析類 – leobelones

問題的答案是二叉樹 – raam86

日誌n表示將陣列2的所有時間，直到你找到它，如二進制搜索...所以你需要知道n的值。

C＃代碼：

的代碼來調用你的函數：

int position = findInteger(array, 0, searchedValue);

功能：

public int findInteger(int[] array, int position, int searchValue) 
{ 
    if(array[position] = searchValue) 
     return position; 
    else if (array[position] > searchValue) 
     position = position/2; 
    else // array[position] < searchValue 
     position = (array.Count() + position)/2; 
    findInteger(array, position, searchValue); 
}

來源

2012-09-20 16:34:00 leobelones

我編輯了答案，因爲我在意外完成之前發送了它 – leobelones

是的，我在想那個，但是如果有重複的話會怎麼樣。即陣列開始時有一百萬個零點。搜索值是10，然後10個來自一百萬個零，所以它不能找到它，因爲它將從0到10看起來。而不是專注於找到x的索引。我怎樣才能找到有多少分類元素？ – ealeon

從它似乎有無限長的陣列問題陳述其中至少有n個條目存在並且按照排序順序。我們假設前n個條目是以升序排列的正整數，如果j> = n，則訪問A [j]返回nil。首先，n是未知的。給定我，問題是確定j使得A [j] == i（或者如果不存在這樣的j<n，則返回nil）。

集合K = 0，L = 1。
雖然真，執行步驟3。
設置k = L和L = 2 * L。如果A [L]爲零，則跳至步驟4.如果A [L]> i跳至步驟5.否則繼續（在步驟2的while循環中）。
現在k < n < L。在A [k：L]中執行二進制搜索以查找最後一個非零條目A [n-1];設L = n-1;然後轉到步驟5
現在A [L]> = I。在A [k：L]中進行二進制搜索以找到i。如果找到它，返回它的索引，否則返回零。

要查看已描述的方法是O（LN n）的有界的，注意，它使用至多2*lg(n)步驟查找N（或L，使得A [L]> i）中，然後在最lg(n)步驟在A [k：L]中找到i，其中lg（n）= ln（n）/ ln（2）。

如果您認爲訪問[J]不返回零，當j> = N，而是返回一個「隨機數」，這種做法打破了;一方面，它可能會發現A [j] ==我但是j> n;另一方面，O（ln n）的時間限制可能不成立，或者只會概率地持有;該算法需要重新檢測以檢測A [L]值序列的減少;如果A是A [n + 1]> A [n]> A [n-1]，那麼無論如何n都不能確定。

來源

2012-09-20 17:22:46

很棒的回答！完善。謝謝。 – ealeon

查找在未知長度的數組x的位置

回答

相關問題