分治法

怼烎@ 2022-06-03 05:52 260阅读 0赞

问题描述:假定一个已经排好顺序的一维数组,运用二分搜索算法,使得当前输入元素x不在数组中是，返回小于x的最大元素位置i和大于x的最小元素的位置j,当搜索元素在数组中，i

和j相同,均为x在数组中的位置.

算法分析:

分治法算法:

void fenzhi(int a\[10\],int x)  
\{   
 int i,flag\_up,flag\_down;  
 int max\_left,max\_right,found\_left,found\_right;  
 for(i=0;i<10;i++)  
 \{   
 if(a\[i\]<x)  
 max\_left=i;  
 else if(a\[i\]==x)  
 found\_left=i;  
 else flag\_down=1;  
 \}  
 for(i=10;i>0;i--)\{   
 if(a\[i\]>x)  
 max\_right=i;  
 else if(a\[i\]==x)  
 found\_right=i;  
 else flag\_up=1;  
 \}  
 if(flag\_down==1)\{   
 printf("Under Out of Index");  
 \}  
 else if(flag\_up==1)\{   
 printf("Up Out of Index");  
 \}  
 else\{   
 if(found\_right!=found\_left)\{   
 printf("%d %d\\n",max\_left,max\_right);  
 \}  
 else  
 printf("found and the place is %d\\n",found\_left);  
 \}  
\}

算法分析:定义一对变量:max\_left和max\_right分别为当x不在数组中时的左右位置;

定义一对变量:found\_left和found\_right分别为当x在数组中时的左右位置;

定义一对变量:flag\_down和flag\_up分别为当x超出我所设定的数组边界时，判断此时是为上边界越线还是下边界越线。

在代码中，首先写一个递增循环，找出三种情况:1.x未超界且x不在数组中时，x的最近左边位置max\_left;2.x未超界且x在数组中时，x的左边位置found\_left;3.x超界时，为下边界；

其次写一个递减循环，找出三种情况:1.x未超界且x不在数组中时，x的最近右边位置max\_right;2.x未超界且x在数组中时，x的右边位置found\_right;3.x超界时，为上边界；

最后就是一系列判断的代码。

完整代码:

\#include<stdio.h>

void fenzhi(int a\[10\],int x)  
\{  
int i,flag\_up,flag\_down;  
int max\_left,max\_right,found\_left,found\_right;  
for(i=0;i<10;i++)  
\{  
if(a\[i\]<x)  
max\_left=i;  
else if(a\[i\]==x)  
found\_left=i;  
else flag\_down=1;  
\}  
for(i=10;i>0;i--)\{  
if(a\[i\]>x)  
max\_right=i;  
else if(a\[i\]==x)  
found\_right=i;  
else flag\_up=1;  
\}  
if(flag\_down==1)\{  
printf("Under Out of Index");  
\}  
else if(flag\_up==1)\{  
printf("Up Out of Index");  
\}  
else\{  
if(found\_right!=found\_left)\{  
printf("%d %d\\n",max\_left,max\_right);  
\}  
else  
printf("found and the place is %d\\n",found\_left);  
\}  
\}  
int main()  
\{  
int a\[10\]=\{1,2,3,4,5,6,7,8,10,11\};  
int x;  
printf("Input the number:");  
scanf("%d",&x);  
fenzhi(a,x);  
return 0;