引子
有有序数据比如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位置的左边
根据上面结果可以设计算法
- 设查找数据左下标为left 右下标为right,中间位置为mid;
- 设置mid为left + (right - left) / 2,即(right + left) / 2;
- 如果key和mid value刚好相等,则mid即为查找结果,返回mid;
- key大于mid value,可以明确key在mid位置的右边,更新left为mid + 1,以left~right为查找数据,从第二步开始重复查找;
- 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; }
程序分析:
- 一开始left为0,right为数据最后一个元素下标;
- 计算mid,如果相等,查找结束,不相等重新确定left或者right,循环重复;
- 也有可能查找整个数据也没有找到,结束条件是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程序分析:
- 计算mid,如果相等,查找结束,返回下标,满足right大于left返回失败值-1;
- 计算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。在实际应用中,使用循环结构实现二分法应该是最好的。
已有 1852 位网友参与,快来吐槽:
发表评论