二分法问题

WTS123456

#include <stdio.h>
#include <stdlib.h>
void main()
{

        int                num[10]={10,9,8,7,6,5,4,3,2,1};
        int                a,i;//a为待查找的数据
        int                begin=0,mid,end=9;

        printf("enter a:\n");
        scanf("%d",&a);

        while(begin<=end)
        {
                mid =(begin+end)/2;

                if(num[mid]==a)
                {
                        printf("这是第%d个数\n",mid+1);
                        break;
                }
                else if(num[mid]<a)
                {
                        end  =mid -1;
                }
                else
                {
                        begin =mid +1;
                }
        }

        if(begin>end)
        {
                printf("zhao bu dao\n");
        }

}

这里num[mid]<a，那么a不应该Mid的左边吗，为什么不是begin =mid +1;

Zmynx_2017

不能是begin = mid + 1 啊，你假设你输入的是 9 ，开始 mid = 4 ，

那么 9 肯定大于 6 ，如果执行 begin =mid +1 这条语句，那么begin = 5，end = 9

然后加起来mid = 7，那么num[mid]离9就是越来越远了，根本然后也不会找到 9

Zmynx_2017

接着刚才的回答，如果执行  end  =mid -1 那么end = 3，下一次mid = 1，刚好num[mid] = 9，也就是找到了

之所以这样，可以这样想，就是你说的，num[mid]<a，那么a不应该Mid的左边，a在mid的左边，说明end有点大了吧，

就是a 的范围应该是begin到mid - 1之间的一个数，所以，把end改为mid - 1没有毛病。