折半查找法（二分法）

• 问题：假设有n个数已按照升序（这是关键！）放在一维数组a中，如何找到你想要的数呢？

• 思路介绍：二分法，顾名思义，把一段数字分成两半。
  你要的数在已经按照升序排好了并且的情况下与中间数进行对比有三种情况：

  1.要么比中间的数大，说明它应该在中间数的右边。那么就可以把右边的边界（right）设置成中间数+1，进一步缩小检索范围。
  2.要么比中间的数小，说明它应该在中间数的左边。那么就可以把左边的边界（left）设置成中间数-1。
  3.要么它就是中间的那个数，此时就不需要再比较了，因为你已经找到了，就可以不用再找了（此处应该要有一个变量设定作为结束的标志），直接输出。

  要注意还有例外情况就是它根本就不在列表里，那自然也怎么找都找不到。（这里与上面能找的情况分为两大宏观条件，要设置if-else语句。没有要求的可忽略）
  那怎么才知道它在不在列表里呢？
  你将它（x）与第一个数和最后一个数进行比较，若x>=a[left](第一个数)，并且x<=a[right](最后一个数)，那它自然就在列表之中了。

• 细节问题：为什么在发现数x比中间数大/小之后，设定left=mid+1和right=mid-1?而不能是left=mid和right=mid?

  这就牵扯到如果中间数有两个（如示意图中的第一次循环的中间数为21、25），那么系统会自动选左边的那个数作为中间数（21）。
  那么当需要检索的是最末尾的数，而最后就剩两个边界，那么无论怎么取中间数，左右边界的范围都不会改变，左边界还是左边界。而你需要检索的数是右边界，即使数确实比中间数大，但是因为算法，中间数永远都不会是右边界，所以永远都不会找到右边界的数。

  但是如果设定为left=mid+1和right=mid-1，这种情况就能够使左边界=右边界，中间数就等于那个数，从而能够进行比较、找到。

我大学老师PPT里的示意图

• 模板

int a[10]={1,2,3,4,5,6,7,8,9,10}; //将a[]改成你想要检索的数组就可以了
int x,left=0,right=9,mid,flag=0; //此处x为要查找的值，right为数组的长度-1，flag为示意找到的变量
 scanf("%d",&x);
 if(x>=a[left]&&x<=a[right])
 while(!flag) // !flag(1)表示没找到，没找到就继续循环直到找到
 { mid=(left+right)/2;
   if(a[mid]==x) flag=1; //找到了就使flag=1，作为循环结束的标志，退出循环
   else if(x>a[mid]) left=mid+1;
        else right=mid-1;
 }
 if(flag==1) printf("a[%d]=%d",mid,x); //找到的时候才可以输出x。这里flag是找到标志，加入判断条件
 else printf("no found!"); //没有需要的可以将它与第一个if语句删除