您好,欢迎访问本站博客!登录后台查看权限
  • 欢迎大神光临
  • 有朋自远方来 不亦悦乎

算法基础 之C语言实现二分法

C/C++ dz2015 2018-08-10 242 次浏览 2个评论

引子

有有序数据比如int data[5] = {1, 2, 3, 4, 5},要在data中查找一个值的位置,程序呼之欲出。

/**
 * 在data中查找key的下标
 * @param data
 * @param dataSize
 * @param key
 * @return key的下标,不存在返回-1
 */
int search(const int *data, int dataSize, int key) {
    for (int i = 0; i < dataSize; ++i) {
        if (data[i] == key) return i;
    }
    return -1;
}

上面方法简单直接,但是我们可以做得更快,这就是我们今天的主题即用二分法优化有序数据查找速度。 二分法查找

二分法

当查找数据是有序时,只要判断中间位置值(mid value)和查找值(key)的大小即可确定会是下面结果之1(假设key一定在数据中):

  • key和mid value刚好相等,则mid即为查找结果
  • key大于mid value,可以明确key在mid位置的右边
  • key小于于mid value,可以明确key在mid位置的左边

根据上面结果可以设计算法

  1. 设查找数据左下标为left 右下标为right,中间位置为mid;
  2. 设置mid为left + (right - left) / 2,即(right + left) / 2;
  3. 如果key和mid value刚好相等,则mid即为查找结果,返回mid;
  4. key大于mid value,可以明确key在mid位置的右边,更新left为mid + 1,以left~right为查找数据,从第二步开始重复查找;
  5. key小于mid value,可以明确key在mid位置的左边,更新right为mid - 1,以left~right为查找数据,从第二步开始重复查找。

实现上面过程可以用for、while、do-while循环实现,也可以用递归实现。

do-while循环实现

/**
 * 在data中查找key的下标
 * @param data
 * @param dataSize
 * @param key
 * @return key的下标,不存在返回-1
 */
int dichotomySearch(const int *data, int dataSize, int key) {
    int left = 0;
    int right = dataSize - 1;
    int mid;
    do {
        mid = (right + left) / 2;
        if (data[mid] == key) {
            return mid;
        } else if (key < data[mid]) {
            right = mid - 1;
        } else { // >
            left = mid + 1;
        }
    } while (right > left);
    return -1;
}

程序分析:

  1. 一开始left为0,right为数据最后一个元素下标;
  2. 计算mid,如果相等,查找结束,不相等重新确定left或者right,循环重复;
  3. 也有可能查找整个数据也没有找到,结束条件是right大于left,查找失败返回特殊值-1。

递归实现

/**
 * 在data中查找key的下标
 * @param data
 * @param key
 * @param left
 * @param right
 * @return key的下标,不存在返回-1
 */
int _recursionDichotomySearch(const int *data, int key, int left, int right) {
    if (right < left) return -1;
    int mid = (right + left) / 2;
    if (data[mid] == key) {
        return mid;
    } else if (key < data[mid]) {
        return _recursionDichotomySearch(data, key, left, mid - 1);
    } else { // >
        return _recursionDichotomySearch(data, key, mid + 1, right);
    }
}

/**
 * 在data中查找key的下标
 * @param data
 * @param dataSize
 * @param key
 * @return key的下标,不存在返回-1
 */
int recursionDichotomySearch(const int *data, int dataSize, int key) {
    return _recursionDichotomySearch(data, key, 0, dataSize - 1);
}

recursionDichotomySearch对_recursionDichotomySearch进行封装,以和search、dichotomySearch有一样的参数形式。 一开始left为0,right为数据最后一个元素下标。

_recursionDichotomySearch程序分析:

  1. 计算mid,如果相等,查找结束,返回下标,满足right大于left返回失败值-1;
  2. 计算key所在的left和right,递归调用_recursionDichotomySearch在left和right区间继续查找。

测试程序

/**
 * 获取当前时间,单位S
 * @return 当前时间,单位S
 */
double timeSec() {
    struct timeval tv;
    gettimeofday(&tv, NULL); // Linux function
    return (double) tv.tv_sec + tv.tv_usec / 1000.0;
}

void test1() {
    int data[500];
    for (int i = 0; i < 500; ++i) {
        data[i] = i;
    }
    double start = timeSec();
    for (int i = -1; i < 501; ++i) {
        int index = search(data, 500, i);
        // printf("test1 index=%d\n", index);
    }
    // $test1 use:0.377000S
    printf("test1 use:%fS\n", timeSec() - start);
}

void test2() {
    int data[500];
    for (int i = 0; i < 500; ++i) {
        data[i] = i;
    }
    double start = timeSec();
    for (int i = -1; i < 501; ++i) {
        int index = dichotomySearch(data, 500, i);
        // printf("test1 index=%d\n", index);
    }
    // $test2 use:0.062000S
    printf("test2 use:%fS\n", timeSec() - start);
}

void test3() {
    int data[500];
    for (int i = 0; i < 500; ++i) {
        data[i] = i;
    }
    double start = timeSec();
    for (int i = -1; i < 501; ++i) {
        int index = recursionDichotomySearch(data, 500, i);
        // printf("test1 index=%d\n", index);
    }
    // $test3 use:0.070000S
    printf("test3 use:%fS\n", timeSec() - start);
}

使用一样的数据对三个算法进行测试,结果:test1明显大于test3大于test2。在实际应用中,使用循环结构实现二分法应该是最好的。

已有 242 位网友参与,快来吐槽:

1#jishu001  2018-08-10 22:16:49 回复该评论
很好 二分法在项目开发中使用频率很高
2#holly  2018-08-25 16:38:47 回复该评论
请问:如果数据是有序浮点数如何改造二分法

发表评论