引子

有有序数据比如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。在实际应用中，使用循环结构实现二分法应该是最好的。