在特定元素上查找排序數組的範圍索引

我正在處理排序集合的數組。任務是查找值的範圍。在特定元素上查找排序數組的範圍索引

讓我們假設我們有這個有序數組：

int[] array = {1,1,1,3,3,9,10}

例我們必須找到元素1.範圍 - min和max我們快速發現該元件1的第1索引0，範圍最大爲2.

我們現在知道0到2之間的範圍都具有值1.如果搜索到的元素是3，我們可以看到該範圍是3-4，對於元素9，範圍是6-6。

我已經使用線性搜索來做到這一點，但會聽到，如果有更快的方法來做到這一點？

來源

2016-09-26 Piqka

您可以使用二進制搜索的兩個版本，找到最左和最右的位置：

int[] array = { 1, 1, 1, 3, 3, 9, 10 } 
int value = ... 

int leftmost(int min, int max) 
{ 
    if (min == max) return min 
    int mid = (min + max)/2 

    if (array[mid] < value) return leftmost(mid + 1, max) 
    else return leftmost(min, mid) 
} 

int rightmost(int min, int max) 
{ 
    if (min == max) return min 
    int mid = (min + max + 1)/2 

    if (array[mid] > value) return rightmost(min, mid - 1) 
    else return rightmost(mid, max) 
}

只是要與min=0和max=array.length-1呼叫。時間複雜度爲O(logn)。

你會得到這樣的（0-based索引）輸出：

value=1 -> left=0, right=2 
value=3 -> left=3, right=4 
value=9 -> left=5, right=5 
value=10 -> left=6, right=6

來源

2016-09-27 13:58:59

時間複雜度將logn，而不是nlog（n） –

@SaurabhVerma謝謝，你是對的。 –

二進制搜索會更快。你可以在這裏得到一些見解here

來源

2016-09-26 21:47:24

與二進制搜索的問題是，它只能返回一個索引。 E.g.如果我們搜索元素1，它將返回1作爲索引。但我正在尋找一個範圍。 – Piqka

假設一個更大的數組與二進制然後是線性的。

根據數組的大小，更快的方式可能是線性的。如果您正在使用像您這樣的7個數字的數組重複執行此搜索，那麼您不會看到太多的性能差異。事實上它可能會變慢。

但是，儘管展開該數組，以便獲得更多的數據，並且最好先進行二分搜索，然後再進行線性搜索。

做一次，抓住範圍的底部，然後做線性查找範圍的終點。

你可以爲結束點做另一個二進制文件，但隨着時間的推移，它應該用一個普通的線性函數平均進行清洗。

來源

2016-09-26 22:00:45 Rodger

在特定元素上查找排序數組的範圍索引

回答

相關問題