折半查找演算法

⑴ 設計折半查找的演算法

/*
這里給出一個int數組的查找
b_sch()函數的參數中第一個為要查找的數組
這個數組必須是有序，我給的這個程序要求從小到大排序
這個數組必須不存在重復元素，否則會影響結果
注意l（L）和1（一）的區別，計算機給出的這兩個字元很相似
*/
intb_sch(int*s,intl,intr,intkey)//s是要查找的數組，l是數組的第一個元素下標
//r是數組最後一個元素下標，key是要查找的元素
{
while(l<=r)//當l<=r時，也就是說在應該查找的范圍內
{
intmid=(l+r)/2;//二分，也就是折半
if(s[mid]==key)//如果mid和要查找的元素相等返回這個下標
returnmid;
elseif(key>s[mid])//如果要查找的元素在mid的右邊，也就是說
//比s[mid]大，那麼說明要查找的元素應該在，mid到r這個區間內
//那麼就把范圍縮小在mid+1到r區間內，所以，最前面的元素下標
//就要改成mid+1，也就是l=mid+1
l=mid+1;
else
r=mid-1;//和上面同理，這個就是右邊元素下標變化
}
return-1;//查找失敗，返回-1
}

⑵ c語言折半查找法

折半查找法是演算法一種，可以被任何計算機語言使用。用C語言自然也可以實現。

1、定義：

在計算機科學中，折半搜索（英語：half-interval search），也稱二分搜索（英語：binary search）、對數搜索（英語：logarithmic search），是一種在有序數組中查找某一特定元素的搜索演算法。

搜索過程從數組的中間元素開始，如果中間元素正好是要查找的元素，則搜索過程結束；如果某一特定元素大於或者小於中間元素，則在數組大於或小於中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。如果在某一步驟數組為空，則代表找不到。這種搜索演算法每一次比較都使搜索范圍縮小一半。

2、查找規則：

折半查找法是效率較高的一種查找方法。假設有已經按照從小到大的順序排列好的五個整數a0~a4，要查找的數是X，其基本思想是： 設查找數據的范圍下限為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，說明沒有此數，列印找不到信息，程序結束。

3、C語言參考代碼：

intbin_search(intA[],intn,intkey){
//在長度為n的數組A中折半查找值為key的元素，並返回下標值。如果不存在則返回-1.
intlow,high,mid;
low=0;
high=n-1;//初始low和high為數組的兩端。
while(low<=high)
{
mid=(low+high)/2;//查找中心點。
if(A[mid]==key)returnmid;//已找到，返回下標值。
if(A[mid]<key){//中點位置比key值小，以mid+1為新的下限值。
low=mid+1;
}
if(A[mid]>key){//中點位置比key值大，以mid-1為新的上限值。
high=mid-1;
}
}
return-1;//未找到，返回-1.
}

⑶ C語言中的折半查找法是什麼

折半查找的前提是已經對數據做好了排序，然後再折半查找
例如排序後的數據是1 5 12 35 64 78 89 123 456
你要查找12，首先用12跟上面排好順序的9個數中間那個比較（64），12<64，因此你查找的數據在前半部分，即
1 5 12 35 64，再用12跟前半部分中間那個數比較（12），這樣找了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小時內寫出完全正確的二分搜索演算法。問題的關鍵在於准確地制定各次查找范圍的邊界以及終止條件的確定，正確地歸納奇偶數的各種情況，其實整理後可以發現它的具體演算法是很直觀的。 剛開始的時候數組時排好順序的：從小到大，或者從大到小。然後將這個數組折中，用中間的這個數和要查找的數比較大小，（例如：如果我從小到大，我將數組這種後，用中間的數和要查找的數比較，如果小

⑷ 用遞歸法寫一個折半查找的演算法

// 二分查找前提數組元素已按升序排序
int binsearch(int value, int a[], int nArrayLen)
{
int nMid = nArrayLen / 2;

if (value == a[nMid])

return nMid; // 找到下標

if (nMid == 0)

return -1; // 找不到

if (value < a[nMid])
return binsearch(value, a, nMid);

else

return binsearch(value, a + nMid, nArrayLen - nMid);

}

⑸ 折半查找法的概念是什麼

對一個已經排好序的數組，先看中間的元素是不是要求元素。如果是就找到了，不是看比要找的元素大還是小，大的話，上前一部分用同樣的方法再找，小的話去後一部分用同樣的方法再找

⑹ 折半查找演算法設計

請查看數據結構朱站立版第，第5、6、10、11章節，先排序，再查找

⑺ 折半查找法的基本演算法實現

bin_search(int A[],int n,int key){
int low,high,mid;
low = 0;
high = n-1;
while(low<=high)
{
mid =(low + high)/2;
if(A[mid]==key)return mid;
if(A[mid]<key){
low =mid + 1;
}
if(A[mid]>key){
high= mid - 1;
}
}
return -1;
} #include <stdio.h>int main()
{
int a[11]={0,1,2,3,4,5,6,7,8,9,10},min=0,max=10,mid,n; //max為數列長度，a[0]作為第一個數組元素
printf(請輸入您要查找的數: );
scanf(%d,&n);
while(min+1!=max)
{
mid=(min+max)/2;
if (n>a[mid]) min=mid;
else if (n<a[mid]) max=mid;
else
{ printf(輸入的數在數列的第%d位 ,mid); break; }
}
if(n==a[max]) printf(輸入的數在數列的第%d位 ,max);
else if(n==a[min]) printf(輸入的數在數列的第%d位 ,min);
else if(n!=a[mid]) printf(輸入的數不在數列中);
return 0;
} #include <stdio.h>
#include <stdlib.h>
void main()
{
int a[15]={1,2,3,4,5,6,7,8,9,10,11,12,13,15};
int n,m,top,bot,mid;
top=m=1; //此處修改top=0;m=1;
bot=14;
printf(please input a number:);
scanf(%d,&n);
while(top<=bot)
{
mid=(top+bot)/2;
if(n==a[mid])
{
printf(這是第%d個元素的值。 ,mid+1);
m=0;
break;
}
else if(n>a[mid])
top=mid+1;
else if(n<a[mid])
bot=mid-1;
}
if(m)
printf(無此數。 );
system(PAUSE);
return 0;
}

⑻ 數據結構折半查找演算法的方法

041424344#include <stdio.h> int Dichotomy(int a[],int _value,int n){ // 二分法(也稱折半查找法) int index=0; // 當前數組的首元素下標 int current=n-1; // 數組當前的大小 int k; // 當前數組中間的數的下標 while (index<current) { // 開始二分法查找 k=(index+current)/2; // 除以2代表得到當前數組中間的數的下標 if(a[k]==_value) return k; // 返回要查找的值_value所在的下標 // 否則比較要查找的值_value是在折半後的前半部分還是後半部分 if(a[k]<_value){ // 說明要查找的值在折半後的後半部分 index=k+1; // 令index指向後半部分數組的首元素 } else{ // 說明要查找的值在折半後的前半部分 current=k-1; // 令current等於前半部分數組的長度 } } return -1; // 返回-1代表沒有查找到該值(_value)}void main(){ int arr[5]={2,12,45,87,95};// 前提是一組數組必須是有序數對(即按小到大或大到小) if(Dichotomy(arr,87,5)!=-1) printf("87在數組中對應的下標是:%d\n",Dichotomy(arr,87,5)); else printf("沒有找到指定的值\n");}// 用一句話概括二分法(折半查找法)的思想就是:在一組有序對數組中反復折半後得到中間數組的下標,然後再進行是否與要查找的值相等,若相等則返回當前要查找的值的下標。 那麼，上面的代碼的注釋與下面一一對應，它在執行的結果會產生兩種情況，第一種,不存在。第二種，存在。先來說說第一種情況 不存在： 1.如果給定要查找的值_value大於數組中最大的數,則index不斷增大從而促使while循環終止 2.如果給定要查找的值_value小於數組中最小的數,則current不斷減少從而促使while循環終止(你自己可以動手在紙上畫一個數組,然後思路跟著代碼走就會知道或設單步調試亦可) 第二種情況 存在： 1.要查找的數_value正好是在數組中間.那麼就執行了一次循環,當然這也是最理想的效果. 否則反復執行2和3:2.如果要查找的數_value不存在中間,則判斷它是否大於中間的數還是小於中間的數,如果小於中間的數則說明_value應該在數組中間的前半部分,那麼current=k-1(即令current等於前半部分的長度),然後仍然採取折半的方法,反復此操作直至找到該數的下標為止. 3.如果要查找的數_value不存在中間,則判斷它是否大於中間的數還是小於中間的數,如果大於中間的數則說明_value應該在數組中間的後半部分,那麼index=k+1(即令index指向後半部分的第一個下標),然後仍然採取折半的方法,反復此操作直至找到該數的下標為止.

⑼ 折半查找的演算法怎麼寫 C語言

#include<stdio.h>
void main()
{
int in[15],ins,i,k=14,j=0;
printf("請按照從小到大的順序輸入15個數\n");
for(i=0;i<15;i++) scanf("%d",&in[i]);
printf("請輸入要查找的數:");
scanf("%d",&ins);
i=(j+k)/2;
while(j<=k)
{
if(in[i]>ins)
k=i-1;
else
if(in[i]<ins)
j=i+1;
else break;
i=(j+k)/2;
}
printf("你查找的是其中的第%d個數。",i+1);/*i是他的存儲的順序數，i+1才是他在輸入數組中的位置數*/
}

⑽ 什麼是折半查找法

#include <stdio.h>
#define N 51
void main(void)
{
int a[N];
int i,n,num;
int top,bottom,mid;
int flag=1; //如果在表列中找到數字，則值為1，否則為0
int loc=-1;//要查找的數在表列中的位置，如果loca=-1表示表列中沒有這個數;如果有這個數,則它的值為所在的位置
printf("你想在多少個數中進行折半查找，請輸入（1--50）：");
scanf("%d",&n);
while(n<1 || n>50)
{
printf("你輸入的數不正確，請重新輸入。\n");
printf("你想在多少個數中進行折半查找，請輸入（1--50）：");
scanf("%d",&n);
}
printf("請你輸入一個整數 a[1](需保證遞增有序):");
scanf("%d",&a[1]);
i=2;
while(i<=n) //輸入從小到大的表列
{
printf("請你輸入一個整數 a[%d](需保證遞增有序):",i);
scanf("%d",&a[i]);
if(a[i] > a[i-1])
i++;
else
printf("你輸入的數不滿足要求，請重新輸入。\n");
}
//輸出表列
printf("\n輸出表列\n");
for(i=1; i<=n; i++)
{
printf("%6d",a[i]);
}
printf("\n");
printf("請你輸入要查找的數：");
scanf("%d",&num);
flag=1; //假設輸入的數在表列中
top=n;
bottom=1;
mid=(top+bottom)/2;
while(flag)
{

//printf("top=%d, bottom=%d, mid=%d, a[%d]=%d\n",top,bottom,mid,mid,a[mid]);
if( (num>a[top]) || (num<a[bottom]) ) //輸入的數 num>a[top] 或者
num<a[bottom]，肯定num不在這個表列中
{
loc=-1;
flag=0;
}
else if(a[mid]==num) //如果num 等於找到的數
{
loc=mid;
printf("找到數 %6d 的位置%2d\n",num,loc);
break;
}
else if(a[mid]>num) //若 a[mid]>num，則num 一定在 a[bottom]和a[mid-1]范圍之內
{
top=mid-1;
mid=(top+bottom)/2;
}
else if(a[mid]<num) //若 a[mid]<num，則num 一定在 a[mid+1]和a[top]范圍之內
{
bottom=mid+1;
mid=(top+bottom)/2;
}
}
if(loc==-1)
{
printf("%d 這個數在表列中沒有找到。\n",num);
}
printf("折半查找結束,按任意鍵退出：\n");

}