查找預排序數組中的兩個元素總和等於某個值

我正在處理作業問題，並且在創建O（n * logn）解決方案時遇到了一些困難。我需要編寫一個函數，它需要一個預先分類的數組和一個值來搜索。然後我需要查找數組中任何兩個元素的和是否等於該值。查找預排序數組中的兩個元素總和等於某個值

我需要創建兩個O（n）和O（N * LOGN）這個算法。 O（n）很容易創建;但是，如果不添加一些實際上無助於解決問題的免費代碼，則無法創建O（n * logn）算法。如果有人可以給我一些關於我可能會錯過的指針，將不勝感激。

2010-02-05 JohnT

你是怎麼做到的O（n）？ – letsc 2011-07-09 17:54:19

@letsc：使用兩個索引a和b;用a = 1和b = n初始化。檢查索引a和b中的元素總和。如果總和是你的目標，停下來，你找到了元素。如果總和較低，則增加一個;如果它較低，則減少b。當a = b時，停止，沒有元素匹配。因爲元素是排序的，所以你只會跳過你認爲不是候選人的對。 – Joubarc 2012-07-04 14:30:08

從第一個元素開始，然後依次執行。儘管如此，使用二分搜索搜索第二個元素。

來源

2010-02-05 01:31:01 AraK

謝謝。我不能相信我錯過了這一點。 – JohnT 2010-02-05 01:35:07

因爲他們是預先排序，你可以使用二進制搜索和線性搜索

來源

2010-02-05 01:31:22

查找預排序數組中的兩個元素總和等於某個值

回答

相關問題