二分算法(2)

  之前，我跟大家讲解了二分算法的基本思想，还有1道二分算法的例题，今天我就给大家再讲一道例题，并且补充一下二分算法的基本思想。

二分算法的基本思想：

      二分法是一个非常高效的算法，它常常用于计算机的查找过程中。

      先玩一个小游戏。预先给定一个小于100的正整数x，让你猜，猜测过程中给予大小判断的提示，问你怎样快速地猜出来？

       这样猜测最快，先猜50，如果猜对了，结束；如果猜大了，往小的方向猜，再猜25；如果猜小了，往大的方向猜，再猜75；…，每猜测1次就去掉一半的数，就这样可以逐步逼近预先给定的数字。这种思想就是二分法。这样子所有的都是靠2的多少次方来解决的，所有效率比枚举快很多了。

      在用二分法进行查找时，查找对象的数组必须是有序的，即各数组元素的次序是按其值的大小顺序存储的。其基本思想是先确定待查数据的范围（可用 [left,right] 区间表示），然后逐步缩小范围直到找到或找不到该记录为止。具体做法是：先取数组中间位置（mid=(left+right)/2）的数据元素与给定值比较。若相等，则查找成功；否则，若给定值比该数据元素的值小（或大），则给定值必在数组的前半部分[left,mid-1]（或后半部分[mid+1,right]），然后在新的查找范围内进行同样的查找。如此反复进行，直到找到数组元素值与给定值相等的元素或确定数组中没有待查找的数据为止。因此，二分查找每查找一次，或成功，或使查找数组中元素的个数减少一半，当查找数组中不再有数据元素时，查找失败。

      二分法查找是一种非常高效的搜索方法，主要原理是每次搜索可以抛弃一半的值来缩小范围，就相当于2的多少次方。其时间复杂度是O(log2n)，一般用于对普通搜索方法的优化， 是比枚举算法快的。

    二分法的适用情况一般满足以下几点：

（1）该数组数据量巨大，需要对处理的时间复杂度进行优化；

（2）该数组已经排序；

（3）一般要求找到的是某一个值或一个位置。

接下来就给大家看几个例题：

例题1二分查找我已经讲过了，就给大家看第二个例题。

例题1的链接：

二分算法(1)

【例2】求平方根 。 

编写一个程序计算x的平方根，x保证是一个非负整数。

      （1）编程思路。

      已求5的平方根为例，说明应用二分法求平方根的思路。

      设  f(x)=x2 ，在 x∈[1,5]的范围内， f(x) 随着 x的增大而增大的（单调递增），这就给二分法创造了条件。

    首先，令浮点型 left 和 right 的初值分别为1和5，然后通过比较 left 和 right 的中点 mid 处  f(x) 的数值与5的大小来选择子区间进行逼近。有以下两种情况：

      1）如果  f(mid)>5，说明当前mid比5的平方根大，应当在 [left,mid]的范围内继续逼近，故令  right=mid;

      2）如果 f(mid)<5，说明当前 mid比5的平方根小，应当在 [mid, right]的范围内继续逼近，故令  left=mid。

   当  right−left<10−5时结束，此时已经满足精度要求，即为所求的近似值。

     其实这道题可以直接使用C++STL库中的sqrt函数来解决。

（2）源程序。

#include 
double f(double x)
 
{
    return x * x;
}
int main()
{
    int x;
    double left,right,mid;
    scanf("%d",&x);
    while (x!=0)
    {
          left=1.0, right=1.0*x;
          while ((right-left)>1e-5)
          {
                mid=(left+right)/2;
                if (f(mid)
                else right=mid;
           }
           printf("%.4f\n",mid);
           scanf("%d",&x);
     }
     return 0;
}

  今天就先讲两道二分算法的题目，明天在讲最后一道。