Question

C语言 二分法查找问题

#include<stdio.h>
int main()
{
int a[10]={0,1,2,3,4,5,6,7,8,9};
int n=7;
int low=0,high=10;
int mid=0;
while(low<=high)
{
mid=(low+high)/2;
if(n<a[mid])
high=mid-1;
else if(n>a[mid])
low=mid+1;
else
printf("%d",mid);
}
return 0;
}
自己写的二分法 为什么一直循环输出 应该怎么改？

Answer 1

#include
<stdio.h>
void
main()
{
float
x0,x1,x2,fx0,fx1,fx2;
do{
printf("enter
x1
&
x2:");
scanf("%f,%f",&x1,&x2);
fx1=(x1*(2*x1-4)+3)*x1-6;
fx2=(x2*(2*x2-4)+3)*x2-6;
}while(fx1*fx2>0);
/*如果f（x1），f（x2）同号，则在[x1,x2]区间无实根，重新输入x1，x2
*/

do{

x0=(x1+x2)/2;
/*求x1和x2间的中点：x0＝(x1＋x2)/2
*/

fx0=(x0*(2*x0-4)+3)*x0-6;

if((fx0*fx1)<0){ /*如f（x0）与f（x1）不同号，把x0赋给x2，把f（x0）赋给f（x2）*/

x2=x0;

fx2=fx0;

}

else{ /*否则，把x0赋给x1，f（x0）赋给f（x1）*/

x1=x0;

fx1=fx0;

}

}while(fabs(fx0)>=1e-5);/*判断f（x0）的绝对值是否小于某一个指定的值（如10的负5次方）*/
printf("x=%6.3f\n",x0);
/*输出x0*/
}

Answer 2

a.txt: 读入数据
b.txt: 写入排序数据
c.txt: 写入查找结果
#include <stdio.h>const int maxn = 1000;int num[maxn], n;void swap(int* x,int* y) { *x ^= *y; *y = *x^*y; *x = *x^*y;}void finput() { printf("--------\nread data from a.txt\n--------\n\n"); FILE* fin = fopen("a.txt","r"); n = 0; while ( fscanf(fin,"%d",&num[n]) != EOF ) { n++; } fclose(fin);}void bubble() { printf("--------\nstart bubbling sort algorithm\n"); for (int i = n-1; i > 0; --i) { for (int j = 0; j < i; ++j) { if (num[j] > num[j+1]) { swap(&num[j],&num[j+1]); } } } printf("write the result of sort in b.txt\n--------\n\n"); FILE* fout = fopen("b.txt","w"); for (int i = 0; i < n; ++i) { fprintf(fout,"%d\n", num[i]); } fclose(fout);}int rbesearch(int low,int high,int v) { // recursive binary search // return the index of v. if not exists, return -1. if (low == high) { if (num[low] == v) return low; return -1; } if (num[low] == v) return low; int mid = (low+high)/2; if (num[mid] < v) { return rbesearch(mid+1,high,v); } else { return rbesearch(low,mid,v); }}int nrbesearch(int low,int high,int v) { // non-recursive binary search // return the index of v. if not exists, return -1. while (low < high) { int mid = (low+high)/2; if (num[mid] < v) { low = mid+1; } else { high = mid; } } if (low == high && num[low] == v) { return low; } return -1;}void search() { printf("--------\n"); printf("Start search.\n"); printf("The results will be written in c.txt\n"); printf("please input a num. if num = -123456, quit.\n"); FILE* file=fopen("c.txt","w"); while (true) { int v; scanf("%d", &v); if (v == -123456) break; int rb = rbesearch(0,n-1,v); int nrb = nrbesearch(0,n-1,v); fprintf(file,"input: %d\n",v); fprintf(file,"the result of recursive binary search: %d\n", rb); fprintf(file,"the result of non-recursive binary search: %d\n\n", nrb); printf("the result of recursive binary search: %d\n", rb); printf("the result of non-recursive binary search: %d\n\n",nrb); } fclose(file); }int main() { finput(); bubble(); search(); return 0;}

Answer 3

#include<stdio.h>
int main()
{
    int a[10]={0,1,2,3,4,5,6,7,8,9};
    int n=7;
    int low=0,high=10;
    int mid=0;
    while(low<=high)
    {
        mid=(low+high)/2;
        if(n<a[mid])
            high=mid-1;
        else if(n>a[mid])
            low=mid+1;
        else
        {
            printf("%d",mid);
            break; //找到了，跳出循环就可以了
        }
    }
    return 0;
}

Answer 4

因为low<=high 找到也会成立，所以一直loop，最后的else语句块加个 break