當前位置:首頁 » 操作系統 » 二分搜索演算法

二分搜索演算法

發布時間: 2022-01-12 03:48:43

『壹』 二分搜索演算法

#include <stdio.h>

#include <stdlib.h>

int a[100]={1,2,3,5,12,12,12,15,29,55};//數組中的數(由小到大)

int k;

void found(int &x,int &y,int k) //在x與y之間,要找k

{

if(x>y)return;

int m=x+(y-x)/2;

if(a[m]==k)x=y=m;

else if(a[m]>k)found(x,y=m-1,k);//找左邊

else found(x=m+1,y,k);//找右邊

}

int main()

{ int i=0,j=9;

scanf("%d",&k);//輸入要找的數字k

found(i,j,k);//從數組a[0]到a[9]中找k

if(i==j)printf("a[%d]==%d ",i,k);

else printf("a[%d]==%d a[%d]==%d, k==%d ",j,a[j],i,a[i],k);

return 0;

}

『貳』 二分搜索演算法是利用什麼實現的演算法

根據分治策略來實現

『叄』 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個,那麼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變數傳到函數里。

『伍』 實現二分搜索演算法,並分析其時間復雜度

對於這樣一個謂詞f(),滿足性質:若f(a)=true,則對於任意定義域內的b>a,f(b)=true.
l與r為值域
int work ( int begin , int end ) {
while ( end - begin != 1 ) {
const int middle = ( begin + end ) / 2 ;
if ( f ( middle ) ) end = middle ;
else begin = middle ;
}
return begin ;
}
返回的是最大的x使f(x)為否

『陸』 改寫二分搜索演算法

小於x的最大元素在x的左邊(x不存在時),大於x的最小元素在x的右邊(x不存在時);所以比較到最後,如果找到x,則輸出x的位置,沒找到x時,返回最後的位置的左和右位置

#include <stdio.h>
int main(){
int ip[100],n,key,i,mid,lt=0,rt,fg=0;
printf("請輸入數組長度:");
scanf("%d",&n);
printf("請輸入已排序的數組:");
for(i=0;i<n;i++)
scanf("%d",ip+i);
printf("請輸入待查找數:");
scanf("%d",&key);
rt=n-1;mid=n/2;
while(mid!=lt)
{
if(ip[mid]==key)
{
fg=1;
break;
}
else
if(ip[mid]>key)
{
rt=mid;
mid=(lt+mid)/2;
}
else
{
lt=mid;
mid=(rt+mid)/2;
}
}
if(fg)
printf("%d\n",mid+1);
else
printf("%d %d\n",mid+1,mid+2);
return 0;
}

『柒』 二分搜索問題

vara:array[1..10]ofinteger;i,j,n,x:integer;beginwriteln('輸入10個從小到大的數:');fori:=1to10doread(a[i]);writeln('輸入要查找的數:');readln(x);i:=1;n:=10;j:=trunc((i+n)/2);repeatifa[j]>xthenbeginn:=j-1;j:=trunc((i+j)/2)endelseifa[j]=n);{為什麼是這個結束循環條件}ifa[j]=xthenwriteln('查找成功!位置是:',j:3)elsewriteln('查找失敗,數組中無此元素!')end.

『捌』 二分查找演算法

前提要求數據排好序,有遞歸和非遞歸版本
int binSearch(const int *Array,int start,int end,int key)
{
int left,right;
int mid;
left=start;
right=end;
while (left<=right) { /注釋中為遞歸演算法,執行效率低,不推薦
mid=(left+right)/2;
/* if (key<Array[mid]) {
return(binSearch(Array,left,mid,key));
}
else if(key>Array[mid]){
return (binSearch(Array,mid+1,right,key));
}
else
return mid;
*/
if (key<Array[mid]) {
right=mid-1;
}
else if(key>Array[mid]){
left=mid+1;
}
else
return mid;
}
return -1;
}

『玖』 用c++語言實現二分搜索演算法

這個就是二分法排序函數的源代碼 傳入參數是數組a和數組的大小n
template <class T>
void BinSort( T a[], int n ) {
int low,high,mid;
for (int i=1; i<n; i++) {
T t=a[i];
low=0; high=i-1;
while (low<=high) {
mid=(low+high)/2;
if (a[mid]>t) high=mid-1;
else low=mid+1;
}
for (int j=i-1; j>=high+1; j--) a[j+1]=a[j];
a[high+1]=t;
}
}

熱點內容
從0至9的反編譯代碼軟體下載 發布:2024-05-28 22:28:50 瀏覽:659
android和web 發布:2024-05-28 22:24:32 瀏覽:465
演算法前途 發布:2024-05-28 22:13:45 瀏覽:360
vs2008資料庫的連接 發布:2024-05-28 22:12:06 瀏覽:464
sqlserver資料庫的復制 發布:2024-05-28 22:10:31 瀏覽:659
如何看老電腦配置 發布:2024-05-28 22:09:27 瀏覽:77
access資料庫的層次 發布:2024-05-28 21:56:22 瀏覽:308
頁面訪問緊急升級新域名 發布:2024-05-28 21:55:38 瀏覽:725
壓縮機管路 發布:2024-05-28 21:26:07 瀏覽:306
安卓結束腳本 發布:2024-05-28 20:40:08 瀏覽:66