實現二分法查找演算法

㈠ 二分搜索演算法的實現

二分搜索的時候，是要慢慢縮小搜索范圍的。比如一共有10個，那麼middle是5,下一層搜索的范圍應該是1-4和6-10。你的函數里沒有這個功能。搜索函數至少應該是int BinarySearch(Type a[], const Type& x,int left, int right);終止條件就是if(left > right) 你定義y的時候是在main函數里，所以BinarySearch裡面不能直接用y，解決方式是在外部定義一個全局的y變數，或者把y變數傳到函數里。

㈡ C語言遞歸函數如何實現二分搜索演算法

折半查找法也稱為二分查找法，它充分利用了元素間的次序關系，採用分治策略，可在最壞的情況下用O(log n)完成搜索任務。它的基本思想是，已知一個有n個元素的有序序列, 將n個元素分成個數大致相同的兩半，取a[n/2]與欲查找的x作比較，如果x=a[n/2]則找到x，演算法終止。如果x<a[n/2]，則我們只要在數組a的左半部繼續搜索x（這里假設數組元素呈升序排列）。如果x>a[n/2]，則我們只要在數組a的右半部繼續搜索x, 直到找到x或者是沒有找到!

如果是常規的方法的話那麼我們可以通過循環的方式, 按照上面說的演算法, 找到則退出循環, 否則繼續循環直到左下標位置小於或者等於右下標的位置.

按兄弟你的意思是要用遞歸方法進行搜索, 那麼大概還是上面的演算法, 只是把循環的方式改成遞歸方式: 如果沒找到,則確定新的搜索范圍, 即左右下標新位置, 然後把新的參數傳給函數繼續調用函數進行遞歸搜索!!

遞歸方式實現詳細代碼如下:

#include <stdio.h>

#define ARRAY_SIZE 10
#define NOT_FOUND -1

int BinarySearch(int array[], int left, int right, int NumToSearch)
{
int mid = (left + right) / 2;

if (left <= right)
{
if (NumToSearch == array[mid])
{
return mid;
}
else if (NumToSearch < array[mid])
{
right = mid - 1;
return BinarySearch(array, left, right, NumToSearch);
}
else
{
left = mid + 1;
return BinarySearch(array, left, right, NumToSearch);
}
}

return NOT_FOUND;
}

int main()
{
int a[ARRAY_SIZE] = {2, 5, 6, 7, 13, 20, 22, 27, 112, 222};//假設一個已知的有序且是升序數列
int result = 0;//查找的結果
int x = 13;//假設我們要查找的數是13
int left = 0;//序列開始下標
int right = ARRAY_SIZE - 1;//序列結尾下標

result = BinarySearch(a, left, right, x);
if (result == NOT_FOUND)
{
printf("Not Found!\n");
}
else
{
printf("Found %d in array a, it is a[%d]\n", x, result);
}

return 0;

}

希望對兄弟你有幫助!

㈢ 在線等~~~建立有10個元素的數組,實現二分法查找演算法

滿意的話，麻煩樓主火速採納一下

#include<stdio.h>
int binsh(int *a, int e, int n)/*a是數組，e是要查找的元素，n是數組總元素的個數，e存在於a的話返回位置，否則返回-1*/
{
int low=0,high=n-1,mid;
for(mid=(low+high)/2;low<=high;mid=(low+high)/2)
{
if(e<a[mid])
high=mid-1;
else if(e>a[mid])
low=mid+1;
else
return mid;
}
return -1;
}
int main()
{
int a[]={1,2,3,4,5,6,7,8,9,0},n;
scanf("%d",&n);
printf("%d\n",binsh(a,n,10));
return 0;
}

㈣ 用順序表實現二分查找演算法

#include<iostream>
using namespace std;
int a[100];
int find1(int l,int r,int x)
{
int m=(l+r)/2;
if(l>r)//查找失敗
return -1;
if(x==a[m])//查找成功返回下標
return m;
else if(x>a[m])
find1(m+1,r,x);//查找右邊
else if(x<a[m])
find1(l,m-1,x);//查找左邊
}
int main()
{//折半查找，待查找數列必須有序(升序或降序)
int x,n,num;
cin>>n;//輸出n待查找數列長度
for(int i=0;i<n;i++)
cin>>a[i];//輸入n個數
cin>>x;//輸入查找值
num=find1(0,n,x);//調用折半查找函數(返回下標)
if(num!=-1)//數組下標0~n-1；返回-1查找失敗
{
cout<<x<<":在數組中的位置 ";
cout<<num<<endl;
}
else
cout<<"查找失敗"<<endl;
return 0;
}

㈤ 二分法查找演算法

哪裡查不到？我復制你的程序，輸入字元c，結果顯示「要查找的字元是第2個」，可以找到

㈥ 二分查找法的具體演算法

折半查找法也稱為二分查找法，它充分利用了元素間的次序關系，採用分治策略，可在最壞的情況下用O(log n)完成搜索任務。它的基本思想是，將n個元素分成個數大致相同的兩半，取a[n/2]與欲查找的x作比較，如果x=a[n/2]則找到x，演算法終止。如果x<a[n/2]，則我們只要在數組a的左半部繼續搜索x（這里假設數組元素呈升序排列）。如果x>a[n/2]，則我們只要在數組a的右半部繼續搜索x。二分搜索法的應用極其廣泛，而且它的思想易於理解，但是要寫一個正確的二分搜索演算法也不是一件簡單的事。第一個二分搜索演算法早在1946年就出現了，但是第一個完全正確的二分搜索演算法直到1962年才出現。Bentley在他的著作《Writing Correct Programs》中寫道，90%的計算機專家不能在2小時內寫出完全正確的二分搜索演算法。問題的關鍵在於准確地制定各次查找范圍的邊界以及終止條件的確定，正確地歸納奇偶數的各種情況，其實整理後可以發現它的具體演算法是很直觀的，我們可用C++描述如下：

template<class Type>

int BinarySearch(Type a[],const Type& x,int n)

{

int left=0;

int right=n-1;

while(left<=right){

int middle=(left+right)/2;

if (x==a[middle]) return middle;

if (x>a[middle]) left=middle+1;

else right=middle-1;

}

return -1;

}

模板函數BinarySearch在a[0]<=a[1]<=...<=a[n-1]共n個升序排列的元素中搜索x,找到x時返回其在數組中的位置，否則返回-1。容易看出，每執行一次while循環，待搜索數組的大小減少一半,因此整個演算法在最壞情況下的時間復雜度為O(log n)。在數據量很大的時候，它的線性查找在時間復雜度上的優劣一目瞭然。

㈦ 使用二分法查找演算法的 前提條件是 被查數據必須是自然數對嗎

前提是被查數據必須有序(升序或降序)。

演算法：當數據量很大適宜採用該方法。採用二分法查找時，數據需是排好序的。

基本思想：假設數據是按升序排序的，對於給定值key，從序列的中間位置k開始比較，如果當前位置arr[k]值等於key，則查找成功；若key小於當前位置值arr[k]，則在數列的前半段中查找,arr[low,mid-1]；

若key大於當前位置值arr[k]，則在數列的後半段中繼續查找arr[mid+1,high]，直到找到為止,時間復雜度:O(log(n))。

(7)實現二分法查找演算法擴展閱讀：

給定精確度ξ,用二分法求函數f(x)零點近似值的步驟如下:

1、確定區間[a,b],驗證f(a)·f(b)<0,給定精確度ξ。

2、求區間(a,b)的中點c。

3、計算f(c).

(1) 若f(c)=0,則c就是函數的零點。

(2) 若f(a)·f(c)<0,則令b=c。

(3) 若f(c)·f(b)<0,則令a=c。

(4) 判斷是否達到精確度ξ:即若|a-b|<ξ,則得到零點近似值a(或b),否則重復2-4。

㈧ 二分法的演算法步驟是什麼

在有序的有N個元素的數組中查找用戶輸進去的數據x。

演算法如下：

1、確定查找范圍front=0，end=N-1，計算中項mid=（front+end）/2。

2、若a[mid]=x或front>=end，則結束查找；否則，向下繼續。

3.、若a[mid]<x，說明待查找的元素值只可能在比中項元素大的范圍內，則把mid+1的值賦給front，並重新計算mid，轉去執行步驟2；若a[mid]>x，說明待查找的元素值只可能在比中項元素小的范圍內，則把mid-1的值賦給end，並重新計算mid，轉去執行步驟2。

(8)實現二分法查找演算法擴展閱讀

基本思想：假設數據是按升序排序的，對於給定值key，從序列的中間位置k開始比較，

如果當前位置arr[k]值等於key，則查找成功；

若key小於當前位置值arr[k]，則在數列的前半段中查找，arr[low，mid-1]；

若key大於當前位置值arr[k]，則在數列的後半段中繼續查找arr[mid+1，high]，

直到找到為止，時間復雜度:O(log(n))。

㈨ 二分法查找的演算法

假如有一組數為3，12，24，36，55，68，75，88要查給定的值24.可設三個變數front，mid，end分別指向數據的上界，中間和下界，mid=（front+end）/2.
1.開始令front=0（指向3），end=7（指向88），則mid=3（指向36）。因為mid>x，故應在前半段中查找。
2.令新的end=mid-1=2，而front=0不變，則新的mid=1。此時x>mid，故確定應在後半段中查找。
3.令新的front=mid+1=2，而end=2不變，則新的mid=2，此時a[mid]=x，查找成功。
如果要查找的數不是數列中的數，例如x=25，當第三次判斷時，x>a[mid]，按以上規律，令front=mid+1，即front=3，出現front>end的情況，表示查找不成功。
例：在有序的有N個元素的數組中查找用戶輸進去的數據x。
演算法如下：
1.確定查找范圍front=0，end=N-1，計算中項mid=（front+end）/2。
2.若a[mid]=x或front>=end,則結束查找；否則，向下繼續。
3.若a[mid]<x,說明待查找的元素值只可能在比中項元素大的范圍內，則把mid+1的值賦給front，並重新計算mid，轉去執行步驟2；若a[mid]>x，說明待查找的元素值只可能在比中項元素小的范圍內，則把mid-1的值賦給end，並重新計算mid，轉去執行步驟2。
[一維數組，折半查找]

㈩ 二分法查找演算法填空

j=r.length-1
//初始時，i和j為整個數組最小和最大的下標；
m=(i+j)/2
//m的值取i和j的中間數；
return
m
//如果這個
k值
等於m，則返回這個
m值
；
j=m-1
//否則如果這個k值小於m，則k只能出現在i到m-1之間；
i=m+1
//否則如果這個k值大於m，則k只能出想在m+1到j之間