求c 程式,折半查詢演算法,C 折半查詢的基本思想和步驟

時間 2022-02-01 19:21:03

1樓:匿名使用者

template

int binary_search( record * r, const int & low, const int & high, const key & k )

else if( low == high )else

return -1;

} //第二個版本的迭代實現(binary_search_v2_iteration)

template

int binary_search( record * r, const int & size, const key & k )

if( low > high )return -1;

else }

2樓:匿名使用者

#include

int search(int low,int high,int n,int num);

void main()

printf("輸入要查詢的數:");

scanf("%d",&n);

printf("%d\n",search(0,19,n,num));

}int search(int low,int high,int n,int num)

給分!!!

c++折半查詢的基本思想和步驟

3樓:佛系執著

折半查詢法是效率較高的一種查詢方法。

基本思想是:設查詢資料的範圍下限為l=0,上限為h=4,求中點m=(l+h)/2,用x與中點元素am比較,若x等於am,即找到,停止查詢;

否則,若x大於am,替換下限l=m+1,到下半段繼續查詢;若x小於am,換上限h=m-1,到上半段繼續查詢;

如此重複前面的過程直到找到或者l>h為止。如果l>h,說明沒有此數,列印找不到資訊,程式結束。

步驟:1、首先確定整個查詢區間的中間位置 mid=( left + right) /2 。

2、用待查關鍵字值與中間位置的關鍵字值進行比較;若相等,則查詢成功,若大於,則在後(右)半個區域繼續進行折半查詢,若小於,則在前(左)半個區域繼續進行折半查詢。

3、對確定的縮小區域再按折半公式,重複上述步驟。最後得到結果:要麼查詢成功,要麼查詢失敗。折半查詢的儲存結構採用一維陣列存放。

擴充套件資料

折半查詢法的優點:比較次數少,查詢速度快,平均效能好;

缺點:是要求待查表為有序表,且插入刪除困難。

因此,折半查詢方法適用於不經常變動而查詢頻繁的有序列表。

4樓:匿名使用者

二分法查詢演算法又叫折半查詢。其思想是將已排好序的數列依次存入陣列,設查詢數值為x,用指標bot指向數列最左端位置(最小值),指標top指向數列最右端位置(最大值),取bot和top的中間值mid指向數列中間。

具體步驟解釋如下:當top>bot時,比較查詢x與a[mid],有3種可能。

若x = a[mid],則表示找到,退出比較查詢。

若x < a[mid],則選擇前半段繼續比較查詢,bot不變,top變成mid-1。

若x > a[mid],則選擇後半段繼續比較查詢,bot變成mid+1,top不變

結束過程有兩種:一種是找到了x = a[mid];另一種是沒找到,即top < bot。

二分查詢也稱折半查詢(binary search),它是一種效率較高的查詢方法。但是,折半查詢要求線性表必須採用順序儲存結構,而且表中元素按關鍵字有序排列。

5樓:清和神子

演算法思想:

折半查詢(binary search)的查詢過程是:先確定等查記錄所在範圍(區間),然後逐步縮小範圍直到找到或找不到該記錄為止。

步驟如下:

比較x和a的中間元素a[mid],

若x=a[mid],則x在l中的位置就是mid;

如果x如果x>a[mid],則x在a[mid]的後面。

無論在哪部分查詢x,其方法都和在a中查詢x一樣,只不過是查詢的規模縮小了。這就說明此問題滿足分治法的第二個和第三個適用條件。

二分查詢也稱折半查詢(binary search),它是一種效率較高的查詢方法。但是,折半查詢要求線性表必須採用順序儲存結構,而且表中元素按關鍵字有序排列。

首先,假設表中元素是按升序排列,將表中間位置記錄的關鍵字與查詢關鍵字比較,如果兩者相等,則查詢成功;否則利用中間位置記錄將表分成前、後兩個子表,如果中間位置記錄的關鍵字大於查詢關鍵字,則進一步查詢前一子表,否則進一步查詢後一子表。重複以上過程,直到找到滿足條件的記錄,使查詢成功,或直到子表不存在為止,此時查詢不成功。

6樓:匿名使用者

#includeusing namespace std;#define n 10 int half(int s,int a,int b,int key) } int main()

答案補充

在對數列查詢之前,可能已經知道了數列的許多相關資訊。比如說,知道了有序數列的大體分佈等。如果知道了有序數列中每相鄰兩個元素之差的最大值的一個上界,這時可以在每次迴圈做折半之前先進行一次篩選工作,把儘可能多的不必要的元素過濾掉,這樣可以極大地提高查詢速度。

其最壞情況下查詢一個元素的最大比較次數將介於1和[ log2 n ] + 1 ( n為元素的個數)之間。另外,在實際的很多應用中可通過在建立有序數列的過程中同時得到m。比如說在建立陣列的過程中可根據插入新元素的情況不斷地更新m,從而在每次查詢的過程中極大地提高效率

7樓:這名字夠隨便

你對對半查詢理解錯了,你的min,max應該是下標而不是值

原理:類似於二分法解方程,二分查詢首先比對序列中間的數是否是要找的數,如果不是,由於是有序數列,則看其在左側區間還是右側區間,捨棄不在的那一半區間,然後在剩餘的區間重複剛才的辦法,直到找到該數,由於每次捨棄一半的資料量,所以查詢效率較高。

描述:設三個變數 left,right,middle分別為序列的兩側下標和中間下標,當判斷出不在左側區間,則 left=middle+1 ,從而利用右側一半構造出一個新區間,否則 right=middle-1,利用左邊一側構造新區間,然後重複剛才過程,如此下去,要麼找到資料,要麼left>right,此時也應該停止查詢,說明序列中沒有該數。

8樓:匿名使用者

折半查詢的基本思想是:對於有序表,查詢時先取表中間位置的記錄關鍵字和所給關鍵字進行比較,若相等,則查詢成功;如果給定值比該記錄關鍵字大,則在後半部分繼續進行折半查詢;否則在前半部分進行折半查詢,直到查詢範圍為空而查不到為止。

折半查詢的過程實際上死先確定待查詢元素所在的區域,然後逐步縮小區域,直到查詢成功或失敗為止。

演算法中需要用到三個變數,low表示區域下界,high表示上界,中間位置mid=(low+high)/2

演算法:#define maxlen n

......

......

int binsearch(datatype a,int k)

return -1; //查詢失敗,返回-1

}這只是演算法,運用要靠你自己!

用c++語言編寫折半查詢演算法的程式

9樓:匿名使用者

#include

#include

using namespace std;

int binary_search(int arr, int len, int val)

return -1;//查詢失敗

}void prtarr(int arr, int len)

int main();

arrlen = sizeof(arr) / sizeof(unsigned int);

prtarr(arr, arrlen);

cout << "輸入要查詢的數:"; cin >> val;

int ret = binary_search(arr, arrlen, val);

if (ret == -1)

cout << "未找到該數" << endl;

else

cout << "該數為陣列的第" << ret << "個元素" << endl;

system("pause");

return 0;

}執行結果:

c++折半查詢法

10樓:匿名使用者

首先,應當宣告兩個變數來記錄這般查詢空間的範圍,這裡我們定義begin和end;其次判斷語句if(x=a[i])中x=a[i]是賦值語句,"=="是判斷相等運算子,應該為if(x == a[i]);最後,主函式為int型,應最後返回0表示執行成功,即在程式結尾家return 0;

以下是我在你**基礎上略加修改,已通過執行併成功。

#include

int main()

else

if (x>a[i])

end = i - 1;

else

begin = i + 1;

}return 0;}

11樓:匿名使用者

你對對半查詢理解錯了,你的min,max應該是下標而不是值原理:類似於二分法解方程,二分查詢首先比對序列中間的數是否是要找的數,如果不是,由於是有序數列,則看其在左側區間還是右側區間,捨棄不在的那一半區間,然後在剩餘的區間重複剛才的辦法,直到找到該數,由於每次捨棄一半的資料量,所以查詢效率較高。

描述:設三個變數 left,right,middle分別為序列的兩側下標和中間下標,當判斷出不在左側區間,則 left=middle+1 ,從而利用右側一半構造出一個新區間,否則 right=middle-1,利用左邊一側構造新區間,然後重複剛才過程,如此下去,要麼找到資料,要麼left>right,此時也應該停止查詢,說明序列中沒有該數。

const int n=10;

int left,right,middle,x;

int a[n]=;

cout << "輸入個要查詢的數: ";

cin>>x;

for (left=0,right=n-1;left<=right;)

{middle=(left+right)/2;

if (x==a[middle])

break;

else if (x

折半查詢法快還是順序查詢快

歲月哪曾斑駁 不能籠統的說那個演算法一定就好,演算法分析要看條件和模型。折半演算法要求待查區域資料是已經排好序的,但是順序查詢沒這個要求。演算法時間分析要看平均情況 最壞情況 最好情況的。最好情況兩者時間一樣,因為都是比較方法查詢,都假定第一次比較就找到。最壞情況,折半查詢更優為log n次比較,而...

C資料庫查詢

有兩種方法 1 建立3個靜態欄位,在登入窗體驗證通過時為這3個欄位賦值,以後其他窗體 資訊管理視窗 再呼叫這賦值後的3個靜態欄位就行了。2 在登入窗體設定3個公有變數,以後其他窗體 資訊管理視窗 再呼叫登入窗體3個公有變數就可以了。你說的 可以在登入視窗那裡用session username tex...

c語言 查詢檔案中的記錄,C語言 查詢檔案中的記錄

include include int find data char name fclose fp printf 沒有這個學生的記錄 n return 1 void main include stdafx.h vc 6.0加上這一行.include stdio.h include string.h ...