论坛 › 数据结构与算法 › 对分查找

mingcxx 发表于 2016-9-25 23:30:55

对分查找

本帖最后由 mingcxx 于 2016-9-25 23:35 编辑

问题描述：实现对分查找使得在每次迭代中只有一个二路比较。
我不太明白“只有一个二路比较”是什么意思？难道是if else语句的分支判断吗？是说条件判断只能有两个分支的意思吗？
那下面这个传统的对分查找算法不是二路比较吗？int binarySearch(const int A[], int N, int X)
{
    int low, high, mid;

    low = 0;high = N - 1;
    while (low <= high)
    {
      mid = (low + high) / 2;
      if (A < X)
            low = mid + 1;
      else if (A > X)
            high = mid - 1;
      else
            return mid;
    }
    return -1;      //not found
}这么写呢？是二路比较么？这个名词第一次听。
int binarySearch(const int A[], int N, int X)
{
        int low, high, mid;

        low = 0; high = N - 1;
        while (low < high)
        {
                mid = (low + high) / 2;
                if (A < X)
                        low = mid + 1;
                else
                        high = mid;
        }
        if (A == X)
                return low;
        else
                return -1;      //not found
}

0洛枫0 发表于 2016-12-2 08:34:34

学习

rayleigh_tong 发表于 2016-12-2 08:35:49

看不懂，进来学习学习

安静的蓝 发表于 2016-12-18 19:55:25

解决好的代码呢

查看完整版本: 对分查找