二進制搜索範圍

我正在製作二進制搜索程序，以查找範圍內左值和右值之間的元素數量。二進制搜索範圍

我的代碼是：

#include<iostream> 
#include<vector> 
#include<algorithm> 
using namespace std; 
vector<int> arr(20); 
int search(int value,int low,int high) 
{ 
    if (high <= low) 
     return low; 
    int mid = (low + high)/2; 

    if (arr[mid] > value) 
     return search(value,low,mid-1); 
    else 
     return search(value,mid+1,high); 
} 


int main(){ 
int n; 
cin>>n; 
//ENTER SORTED ARRAY 
for(int i=0;i<n;i++){ 
    cin>>arr[i]; 
} 


int left; 
cin>>left; 
//RIGHT IS GREATER OR EQUAL TO LEFT 
int right; 
cin>>right; 
cout<<search(right,0,n-1)-search(left,0,n-1)+1<<"\n"; 

}

它給正確的答案一定範圍內。
但是對於一些給出錯誤的情況，如果N = 6且數組爲[1 3 5 8 10 13]並且說範圍爲[5,9]，那麼它給出1作爲答案，但它應該爲2爲5和8兩者都在範圍內。

來源

2014-03-13 user3405426

這可能會或可能不會涉及到你的問題，但我很好奇，你會想這個算法給您例如用'n ==可0'設置什麼答案？看起來你的算法不能給出區分範圍中的1個元素和範圍中的任何元素的答案。 –

@MichaelBurr我假設左右都是我的數組範圍 – user3405426

http://coliru.stacked-crooked.com/a/c2e49c838d017ace –

一個問題是，當arr[mid] == value，你只是忽略它，遞歸到右邊。

您需要將mid包括在您的正確範圍內，或者如果arr[mid] == value返回mid。

我還看到重複值（如果可能的話）是一個問題 - 當遞歸找到最左邊的位置時，需要找到第一個重複值，當遞歸找到最右邊的位置時，需要找到最後一個重複值，所以沒有標誌的單個函數可以指示我們正在做的是不是工作。爲了說明問題：

如果範圍[5,5]和輸入[1,2,5,5,5,6,8]，同樣的遞歸調用找到的5位置將總是返回相同的5的位置，在那裏，因爲你需要回報指數2爲左側範圍和索引4爲正確，以獲得3作爲您的輸出。

來源

2014-03-13 06:47:22 Dukeling

他們沒有重複。 – user3405426

試試這個

int search(int value,int low,int high) 
{ 
if (high <= low) 
    return low; 
int mid = (low + high)/2; 
if(arr[mid]==value){  // add this line it would be work for you 
    return mid; 
} 
if (arr[mid] > value) 
    return search(value,low,mid-1); 
else 
    return search(value,mid+1,high); 
}

，並在main（）

cout<<search(right,0,n-1)-search(left,0,n-1)<<"\n";

來源

2014-03-13 06:48:25

它仍然是上面的例子 – user3405426

給予1，因爲9是不存在於您列出所以它的起飛10日現在的位置值 –

但在我的代碼，它完美地工作，如果任一數字存在或不 –

修正沒有檢查arr[mid]可以==值。在你的例子中，對於left == 5的第一次迭代給出了mid ==（0 +（6-1））/ 2 = 5/2 = 2，arr [2]恰好是5.我們應該停下來，但是你的代碼進入分支search(5, 3, 5);

來源

2014-03-13 06:48:44

，如果你想找到那些在[左，右]範圍內的arr元素的數量你的程序的邏輯似乎是錯誤的，試試這個：

int i; 
int count = 0; 
for(i = 0; i < n; i++) { 
    if (arr[i] >= left && arr[i] <= right) 
     count++; 
}

如果你堅持用二進制搜索試試這個：

static int search(int value,int low,int high) 
{ 
    if (high <= low) 
     return low; 
    int mid = (low + high)/2; 
    if (arr[mid] == value) 
     return mid; 
    int idx; 
    if (arr[mid] > value) 
     idx = search(value,low,mid-1); 
    else 
     idx = search(value,mid+1,high); 
    if (value == arr[idx]) { 
     return idx; 
    } 
    else { 
     if(value > arr[idx]) 
      return mid +1; 
     else 
      return mid; 
    } 
}

來源

2014-03-13 06:53:51 mok

您誤解了這個問題。 – user3405426

@ user3405426：我得到的結果是，你有{1,3,5,8,10,13}這樣的東西，並且想要找出其中有多少在[5,9]範圍內，是不是錯誤？ – mok

爲什麼要在arr中搜索5和9？ – mok

int search(int value,int low,int high) 
{ 
    if (high <= low + 1) 
     return low; 
    int mid = (low + high)/2; 

    if (arr[mid] > value) 
     return search(value,low,mid); 
    else 
     return search(value,mid,high); 
}

而在你的主要功能

cout<<search(right+1,0,n-1)-search(left,0,n-1)<<"\n";

來源

2014-03-13 07:40:10 gloompisces

二進制搜索範圍

回答

相關問題