二分法怎么找偶数(最适合新手的折半查找)
二分法怎么找偶数(最适合新手的折半查找){ int calculate(int x) #include <iostream> #include<stdio.h> using namespace std;
二分法即设头,尾,中三个变量以low,high,mid表示。mid=(low high)/2,每次以mid对应的值进行比较,若索要查找的值>mid对应的值,则low=mid,反之high=mid。之后再以新的low,high求新的mid对应查找,直至找到。部分时候以high>=low作为条件避免重复查找。
类型一:二分法求解
例:8x^4 7x^3 2x^2 3x 6=y,输入y的值,求[0 100]的解
[cpp] view plain copy print?
-
#include <iostream>
-
#include<stdio.h>
-
using namespace std;
-
int calculate(int x)
-
{
-
return 8*x*x*x*x 7*x*x*x 2*x*x 3*x 6;
-
}
-
int main()
-
{
-
int y;
-
double high=100 low=0 mid;
-
while(cin>>y)
-
{
-
while(low-high<1.0e-6) / /循环至high,low近乎相等
-
{
-
mid=(high low)/2;
-
if(calculate(mid)<y)
-
low=mid;
-
else
-
high=mid;
-
}
-
printf("%.4lf\n" high);
-
}
-
return 0;
-
}
int high=n-1 low=0 mid;
while(low<=high)
{
mid=(high low)/2;
if(num[mid]==x)
break;
if(num[mid]<x)
low=mid;
else
high=mid;
}
cout<<mid<<endl;
int high=n-1 low=0 mid;
while(low<=high)
{
mid=(high low)/2;
if(num[mid]==x)
break;
if(num[mid]<x)
low=mid;
else
high=mid;
}
cout<<mid<<endl;
不写全了,领会即可。演示过程如下:
设num数组8 10 12 16 18 20 23 24 28 33 43 55 查找元素为24
low mid high
第一次比较 8 10 12 16 18 20 23 24 28 33 43 55
low mid high
第二次比较 8 10 12 16 18 20 23 24 28 33 43 55
low midhigh
第三次比较 8 10 12 16 18 20 23 24 28 33 43 55
low mid high //num[mid]==x break;
以一道C语言编程题为例
15个数有大到小排列后输入一个数,用折半法查找在数列中的位置
#include<stdio.h>
int main()
{ int a[15] i j t flag=1 number sign=0 top=0 bott loca;
for (i=0;i<15;i )
{printf("输入十五个整数:\n");
scanf("%d" &a[i]);
for(i=0;i<15;i )
for(j=0;j<15-i;j )
{if (a[j]<a[j 1])
{t=a[j]; a[j]=a[j 1];a[j 1]=a[j];} } /* 此处是对输入的15个元素的冒泡排序*/
while(flag)
{printf("input number to look for:");
scanf("%d" &number);
sign=0;
top=0;//top是查找区间的起始位置
bott=N-1;//bott是查找区间的最末位置
if ((number<a[0])||(number>a[N-1]))//要查的数不在查找区间内
loca=-1;// 表示找不到
while ((!sign) && (top<=bott))
{mid=(bott top)/2;
if (number==a[mid])
{loca=mid;
printf("Has found %d its position is %d\n" number loca 1);
sign=1;
}
else if (number<a[mid])
bott=mid-1;
else
top=mid 1;
}
if(!sign||loca==-1)
printf("cannot find %d.\n" number);;
printf("continu or not(Y/N)?");
scanf(" %c" &c);
if (c=='N'||c=='n')
flag=0;
}
return 0;
}
新手最好掌握此方法,冒泡和二分都是C语言重要的基础算法。