二分法

代码实现

以下是一个简单的例子：根据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. 二分法为什么会陷入死循环？

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

  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 打印出来看看，以判断死循环原因