二進制搜索的邏輯

我讀了數據結構手冊中的二進制搜索的僞代碼，然後開始編寫代碼。我寫的代碼是：二進制搜索的邏輯

#include <iostream.h> 
#include <conio.h> 
template <class T> 

int BSearch(T x[], const int n, T item) 
    { 
    int loc, first = 0, found = 0, last = n-1; 
     while(first <= last && !found) 
     { 
      loc = (first + last)/2; 
      if(item < x[loc]) 
       last = loc - 1; 
      else if(item > x[loc]) 
       first = loc + 1; 
      else 
       found = 1; 
     } 
     return found; 
    } 

int main() 
    { 
    const int n =5; 
     int x[n],item; 
     cout << "Pls enter " <<n<<" number(s): "; 

     for(int i = 0; i < n;i++) 
     cin >> x[i]; 
     cout << "Pls enter the item to Search: "; 
     cin >> item; 
     if(BSearch(x,n,item)) 
     cout << "\n\t Item Exist"; 
     else 
     cout << "\n\t Item NOT Exist"; 

     getch(); 
     return 0; 
    }

沒有任何錯誤，但是存在邏輯錯誤。它只是從BSearch函數返回0值，我只是得到這個消息「Item Not Exist」。我的錯誤在哪裏？我沒有找到它。謝謝

來源

2012-12-17 John Martin

當你用調試器加入代碼時發生了什麼？ –

@irrelephant：在書中作者說「last < - loc -1」 –

請注意，在_Sorting and Searching_的6.2.1節中，Knuth記錄了第一個二進制搜索例程於1946年發佈，但第一個發佈的二進制搜索沒有錯誤的程序直到1962年纔出現。令人驚訝地很難得到正確的二進制搜索！ –

二進制搜索僅適用於有序列表。但是您不要訂購從std::cin獲得的列表，因此您從二分查找中得到了錯誤的結果。

要解決這個問題，您必須將輸入限制爲預先排序的列表，或者您必須在執行二分查找之前首先對列表進行排序。

來源

2012-12-17 01:01:56 Haatschii

你能幫我寫一個適用於無序列表的二進制代碼嗎？ –

@JohnMartin - 在無序列表上工作的唯一Binary搜索算法是在搜索之前對其進行排序的算法。 –

@JohnMartin Karthik T說的是真的。因此，如果是作業，您應該再次閱讀說明書，如果您可以將已排序的列表視爲理所當然。我會懷疑是否，因爲有效地對列表進行排序比雙向搜索更有效。如果你確實需要它的一些程序，我會建議你使用標準庫算法。特別是http://en.cppreference.com/w/cpp/algorithm/find和http://en.cppreference.com/w/cpp/algorithm/sort可能會有幫助。 – Haatschii

我試了你的代碼，它似乎工作正常。你必須記住，你輸入的數字必須從小到大排列。

來源

2012-12-17 01:23:14

二進制搜索涉及通過將範圍劃分爲原始大小的一半來將搜索範圍縮小爲一半。二進制搜索按排序後的數組運行。它將該範圍中間的元素與要搜索的值進行比較，如果值小於中間值，則在從第一個元素到中間的範圍內查找該值，否則新搜索範圍將變爲中間到最後的元素。這個過程一直持續到所需的元素被定位，或者下限變得大於上限。二進制搜索的效率平均爲O（log2n），最差情況下爲O（1）。執行二進制搜索的'C'程序如下：

/* Binary Search */ 
#include <stdio.h> 

#define MAX 10 

int main(){ 
int arr[MAX],i,n,val; 
int lb,ub,mid; 
printf(「nEnter total numbers?」); 
scanf(「%d」,&n); 
for(i=0;i<n;i++){ 
printf(「nEnter number?」); 
scanf(「%d」,&arr[i]); 
} 
printf(「nEnter the value to search?」); 
scanf(「%d」,&val); 
lb=0;ub=n-1; 
while(lb<=ub){ 
mid=(lb+ub)/2; 
if(val<arr[mid]) 
ub = mid-1; 
else if(val>arr[mid]) 
lb = mid+1; 
else { 
printf(「nNumber found…!」); 
return; 
} 
} 
printf(「nNumber not found…!」); 
}

來源

2012-12-18 05:56:21

二進制搜索的邏輯

回答

相關問題