尋找排序數組中綁定給定值的兩個連續值的優雅方式？

Question

我有一個有序的整數數組，我想獲得兩個連續的元素索引，這些元素綁定了我傳入的特定值。爲了說明這一點，因爲很難用單詞來描述，我們假設我有一個數組定期零索引）：

1 3 4 5 7 9 

我想要得到的是約束，比方說兩個指數，值6在這種情況下，所述陣列具有值5和7在連續的位置，其結合I」的值（5 < = 6 < = 7），所以我會返回索引5和索引7（分別是3和4）。

我有一個非常蠻力的時尚，這涉及到很多排序和搜索數組。另外，我覺得我錯過了很多角落案例（特別是值大於/小於數組中最大/最小值的值）。

有沒有一個這樣做的優雅方式？我應該注意哪些角落案例，以及如何處理和檢查它們？謝謝！

Answer 1

您可以使用二進制搜索解決問題，在O（lg（n））中解決它，而不考慮這麼多邊界情況。這個想法是使用二進制搜索來找到大於或等於要綁定的值的最小元素（我們稱之爲x）。

pair<int, int> FindInterval(const vector<int>& v, int x) { 
    int low = 0, high = (int)v.size(); 
    while (low < high) { 
    const int mid = (low + high)/2; 
    if (v[mid] < x) low = mid + 1; 
    else high = mid; 
    } 
    // This if is used to detect then a bound (a <= x <= x) is impossible but a 
    // bound (x <= x <= can be found). 
    if (low == 0 && low < (int)v.size() && v[low] == x) ++low; 
    return make_pair(low - 1, low); 
} 

注意，答案可能是(-1, 0)，表明沒有下界的間隔，這可能是(n - 1, n)，這表明不存在上限的間隔（其中，n是v大小） 。另外，如果x在v中，則可以有兩個可能的答案，並且如果x在v中多次出現，則可以有多個答案，因爲邊界包括極值。

最後，您也可以替換與std::lower_bound功能的二進制搜索：

pair<int, int> FindInterval(const vector<int>& v, int x) { 
    // This does the same as the previous hand-coded binary search. 
    const int low = (int)(lower_bound(v.begin(), v.end(), x) - v.begin()); 

    // The rest of the code is the same... 
} 

Answer 2

基本上：

1. 排序陣列（一次）;
2. 做一個二分查找找到最接近的元素;
3. 將該元素與輸入值進行比較;
   • 如果它較低，則有下限;
   • 如果它更高，你有更高的界限;
   • 如果它是相同的，則邊界位於元素旁邊。現在

如果你能在陣列中重複值的最後一步是更復雜一點。您可能需要跳過幾個值。

最終，這只不過是一個有序排列數組上的二分搜索而已，排序數組上的O（log n）和未排序數組上的O（n log n）也是如此。

Answer 3

使其更快的一種方法是使用binary search。這將減少您當前的時間複雜度爲O（n）至O（log n）。

Answer 4

二進制搜索所需的值（在本例中爲6）。

如果找到，則根據生成的索引獲取上一個值和下一個值。

如果不是，您的最終搜索值將小於 或大於您的目標值。如果它更大，那麼您的邊界值將位於該索引和前一個索引處。否則，他們將在該索引處和下一個索引處。