二分法

代码实现

以下是一个简单的例子：根据ADC值查找对应温度值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
unsigned short ADC_Table[101] = {
    3999,
    3967, 3961, 3954, 3947, 3940, 3932, 3924, 3916, 3907, 3899,
    3889, 3880, 3870, 3860, 3850, 3839, 3827, 3816, 3804, 3791,
    3779, 3766, 3752, 3738, 3724, 3708, 3693, 3676, 3660, 3643,
    3625, 3607, 3589, 3570, 3550, 3530, 3510, 3489, 3468, 3446,
    3424, 3401, 3378, 3354, 3330, 3306, 3281, 3255, 3229, 3203,
    3175, 3146, 3117, 3088, 3058, 3028, 2997, 2966, 2935, 2903,
    2871, 2839, 2806, 2774, 2741, 2707, 2674, 2640, 2607, 2573,
    2539, 2505, 2471, 2436, 2402, 2368, 2334, 2300, 2265, 2231,
    2197, 2163, 2130, 2096, 2063, 2028, 1993, 1959, 1925, 1891,
    1857, 1823, 1790, 1758, 1725, 1693, 1661, 1630, 1599, 1580
};

/**
 * @brief       查询ADC对应温度
 * @param[1]    arr ADC数组
 * @param[2]    left right 数组的首末下标
 * @param[3]    x 实时获取的ADC值
 */
int adc_search(const unsigned short* arr, unsigned char left, unsigned char right, unsigned short x)
{
    if (x >= arr[0])
    {
        return 0;
    }
    if (x <= arr[100])
    {
        return 100;
    }

    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        if (arr[mid] >= x && arr[mid + 1] <= x)
        {
            return mid + 1;
        }
        else if (arr[mid] <= x)
        {
            right = mid - 1;
        }
        else if (arr[mid] >= x)
        {
            left = mid + 1;
        }
    }
    return -1;
}

// 调用
adc_search(ADC_Table, 0, 100, ntc_adc);

注：以上二分法只适用于数组按降序排列的情况，如按升序排列，则需稍作修改，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int adc_search_up(const unsigned short *arr, unsigned char left, unsigned char right, unsigned short x)
{
    if (x <= arr[0])
    {
        return 0;
    }
    if (x >= arr[TABLE_NUM - 1])
    {
        return (TABLE_NUM - 1);
    }

    while (left <= right)
    {
        unsigned short mid = left + (right - left) / 2;
        if (arr[mid] <= x && arr[mid + 1] >= x)
        {
            return mid + 1;
        }
        else if (arr[mid] > x)
        {
            right = mid - 1;
        }
        else
        {
            left = mid + 1;
        }
    }
    return -1;
}

二分法

另一种实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#define TABLE_NUM (140)

unsigned short Bat_Table[TABLE_NUM] = {
    3903, 3892, 3881, 3869, 3857, 3844, 3831, 3817, 3803, 3788,
    3772, 3756, 3739, 3722, 3704, 3685, 3666, 3646, 3625, 3604,
    3582, 3559, 3536, 3512, 3487, 3462, 3436, 3409, 3382, 3354,
    3325, 3295, 3265, 3235, 3203, 3172, 3139, 3106, 3072, 3038,
    3004, 2968, 2933, 2897, 2860, 2823, 2786, 2748, 2711, 2672,
    2634, 2595, 2556, 2517, 2478, 2439, 2400, 2360, 2321, 2282,
    2243, 2203, 2164, 2125, 2087, 2048, 2010, 1972, 1934, 1896,
    1859, 1822, 1785, 1749, 1713, 1678, 1643, 1609, 1574, 1541,
    1508, 1475, 1443, 1411, 1380, 1349, 1319, 1289, 1260, 1232,
    1203, 1176, 1149, 1122, 1096, 1071, 1046, 1021, 997, 974,
    951, 928, 906, 885, 864, 843, 823, 804, 784, 766,
    747, 730, 712, 695, 679, 662, 646, 631, 616, 601,
    587, 573, 559, 546, 533, 520, 508, 496, 484, 473,
    462, 451, 440, 430, 420, 410, 401, 391, 382, 373

};

int adc_search(const unsigned short *arr, signed short left, signed short right, unsigned short x)
{
    if (x >= arr[left])
    {
        return left;
    }
    else if (x <= arr[right])
    {
        return right;
    }

    while (left <= right)
    {
        int mid = left + (right - left) / 2;

        if (arr[mid] == x)
        {
            return mid;
        }
        else if (arr[mid] < x)
        {
            right = mid - 1;
        }
        else if (arr[mid] > x)
        {
            left = mid + 1;
        }
    }

    unsigned short diff_left = (arr[left] > x) ? (arr[left] - x) : (x - arr[left]);
    unsigned short diff_right = (arr[right] > x) ? (arr[right] - x) : (x - arr[right]);

    return (diff_left <= diff_right ? left : right);
}

问题

  1. 二分法为什么会陷入死循环？

判断条件选取的不对，多一个 = 就有可能陷入死循环；另外数组最好为单数，双数极可能陷入死循环

  1. 为什么 while (left <= right) 用 <= 不用 < ？

因为 right 的值为 数组元素个数 - 1 ，这时 left 与 right 是可以相等的

  1. 为什么取中间数要写成 int mid = left + (right - left) / 2; 这样？

因为若 left + right 很大的时候会发生整形溢出，这样写可以尽量避免

  1. 为什么判断条件写成 if (arr[mid] >= x && arr[mid + 1] <= x) 这样？

因为数组元素为 unsigned short 型，不会出现浮点数，且数组元素不是等差为1的等差数列，不是非此即彼，可能会出现 arr[mid] >= x && arr[mid + 1] <= x 这种情况

  1. 建议：遇到死循环将 left right mid 打印出来看看，以判断死循环原因