在二進制搜索中搜索排序數組的複雜度較低

要搜索一個非常大的數組，我在考慮一個複雜度小於log n的算法，這意味着它的順序不是小於log n的順序，但絕對小於log n.So我所做的並不是走到中間，而是向前移動一步，並檢查如果數字均勻分佈，我們必須進一步移動，移動到那個位置，如果這是一個解決方案，則另行計算我們必須移動多少futher，做反覆，直到找到解決方法這裏有一個工作Java代碼： -在二進制搜索中搜索排序數組的複雜度較低

public class Search { 
     public static void main(String[] args) { 
      int a[]={12,15,16,17,19,20,26,27}; 
      int required=27; 
      int pointer=0; 
      int n=1; 
      int diff; 
      int count=0; 
      int length=a.length; 
      while(a[pointer]!=required){ 
       count++; 
       if ((pointer+n)>(length-1)) 
        n=length-1-pointer; 
       if(n==0) 
        n=-1; 
       diff=a[pointer+n]-a[pointer]; 
       pointer=pointer+n; 
       n=(required-a[pointer])*n/diff; 


      } 
      System.out.println(pointer); 
      System.out.println(count); 
     } 

    }

PS-我有一個數組是接近均勻分佈。

我想問一下它是否比二分查找更好？在哪些情況下它會失敗？什麼是最好的，平均的和最差的情況下的複雜度？

來源

2014-10-27 user1598240

你在做什麼是一個糟糕的主意，幾乎在任何情況下都會減慢你的搜索速度。 – 2014-10-27 11:04:46

@Rafael你能解釋一下爲什麼？ – user1598240 2014-10-27 11:06:54

唯一比二進制搜索更快的搜索是哈希。 O（1）複雜性。除此之外，二元搜索在複雜性方面幾乎是您所期望的最好的。 – TuanDT 2014-10-27 11:41:16

您正在使用試探法來嘗試加速排序。啓發式就像猜測。不能保證是正確的 - 但如果啓發式是好的，可以在一般情況下加速算法。

啓發式算法通常不會改進算法的最壞情況運行時間。那就是 - 啓發式的某些輸入可能是錯誤的。

我可以看到你正在做的事情的直觀吸引力 - 你正在「搜索」更接近你認爲你的目標可能在哪裏。

但有兩個問題，你在做什麼：

移動在二進制搜索的「分裂」更接近目標不加快搜索速度。在二進制搜索中，您每次將搜索空間分成一半。當你將分割點移近目標時，你沒有找到目標，並且它很可能是你所瞄準的目標不在兩個不相等的空間中較大的那個。

例如，假設您有以下數組。 y爲你的目標，X是所有其他值：

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxYxx

在二進制搜索，你會在半前兩項決定分開的空間，然後再半：

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxYxx 
       ^ ^

兩個決定後你的32值數組下降到8個值的搜索空間。但是，假設你的啓發式，在第二選擇後，你把分裂後的y？

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxYxx 
       ^   ^

在您的第二個決定後，您只減少了一點搜索空間。通過增加這種啓發式，你已經將最壞情況下的運行時間減少到了N - 因爲有可能構建輸入來欺騙你的啓發式，從而每次都做出最糟糕的猜測。

另一個問題是，啓發式方法來加速搜索只有當你知道你正在搜索的東西有幫助。以字典搜索。你知道z在字母表的末尾。所以當你得到一個以z開頭的單詞時，你很清楚在字典中z字的位置。你不必在字典中間開始。

這是因爲你知道一些字典在詞典中的分佈。但是，如果某人對列表中的單詞不作任何保證 - 那麼您無法保證字典搜索速度更快 - 例如，您可能會收到所有z單詞的列表。

在你的情況下，你的啓發式不是特別好。您正在猜測下一個分割的基礎是當前分割和前一個分割之間的距離。如果列表中的元素是均勻間隔的，那麼唯一可以猜測的時間是。如果它們不均勻分佈（幾乎總是），那麼一些猜測總是會超出分裂和其他下衝。

在不均勻間隔數的任何排序數組中，必定存在間隔比平均間隔更緊密的間隔，並且間隔比平均更稀疏。你的啓發式猜測在當前拆分到數組末尾的數字的平均稀疏度上。這兩件事之間沒有任何關係。您的最佳案例時間：O（1） - 例如，您的最佳案例時間：O（1） - 例如，你猜對了索引。最壞情況：O（N） - 例如，每一個選擇都是最糟糕的。

您補充說您的陣列幾乎均勻間隔且非常大。我猜測在實踐中最快的是：查找數組中的第一個數字和最後一個數字，以及數組的長度。使一個受過教育的猜測你的目標的偏差：

offset = floor(((target - first)/(last - first)) * length);

之所以選擇在目標周圍一個合理的搜索空間：

window_start = floor(offset * (1 - alpha)); 
window_end = floor(offset * (1 + alpha));

做這個窗口中定義的子陣列上的二進制搜索。

你設置alpha的方式取決於你認爲你的數組是多麼規則。例如。您可以將其設置爲0.05，以搜索大約佔估算目標周圍總搜索空間10％的窗口。

如果您可以對輸入的均勻性做出一些保證，那麼您可能會優化調整alpha。

來源

2014-10-27 13:48:16

謝謝你這麼好的解釋。你的猜測算法是完美的，但有一個問題。毫無疑問，我有一個非常大的數組，它是接近均勻distibuted，但它在大多數情況下並不總是。所以這是不可能的決定alpha.Hence，我想我必須把我的解決方案只實施。 – user1598240 2014-10-28 06:39:36

在二進制搜索中搜索排序數組的複雜度較低

回答

相關問題