假设在有序线性表A[1..30]上进行二分查找,则比较五次查

[单选题]

假设在有序线性表A[1..30]上进行二分查找,则比较五次查找成功的结点数为（）

```
8
```
```
12
```
```
15
```
```
16
```

查看答案及解析

闲云人

2的4次方–1=15，30–15=15

发表于 2020-07-04 09:44:05 回复(0)

飞飞zZ

30-(2^4-1)

发表于 2020-04-07 10:42:58 回复(0)

cainiao23333

按照完全二叉搜索树构建即可数出来

发表于 2019-07-18 16:59:03 回复(0)

hjZhang

线性表长度为n，二分查找比较k次，若k不是最下面一层，那么比较成功的结点数为2^k-1，若k是最下面一层，也即2^k>=n，那么结点数为n-(2^k-1-1)

发表于 2021-04-07 10:40:45 回复(0)

牛客442823001号

30-（2⁴-1）=15，n层排满二叉树的节点总数为2ⁿ-1

发表于 2020-03-17 16:25:21 回复(0)

叫我皮卡丘

我们可以画出二分查找的搜索路径树：

编辑于 2019-08-06 20:55:00 回复(7)

兰陵王＆阿兰朵

答：查找一次成功的节点数为1，值为15

查找二次成功的节点数为2，值为7,,23

查找三次成功的节点数为4,值为3,11,19,27

查找四次成功的节点数为8，值为1,5,9,13,17,21,25,29

查找五次成功的节点数为15，值为2,3,4,6,8,10,12,14,16,18,20,22,24,26,28，30

发表于 2019-05-30 19:29:32 回复(4)

chasein

写了一段代码测试了一下

public class BinarySearch {
    static Map<Integer, Integer> map = new HashMap<>();
    public static void main(String[] args) {
        int[] a = new int[30];
        for (int i = 0; i < a.length; i++) {
            a[i] = i + 1;
        }
        for (int i = 0; i < a.length; i++) {
            binarySearch(a, a[i]);
        }
        for (Map.Entry entry : map.entrySet()){
            if (entry.getValue() == (Integer)5){
                System.out.println(entry.getKey() + ":" + entry.getValue());
            }
        }
    }

    static Map<Integer, Integer> binarySearch(int[] a, int key){
        int low = 0;
        int high = a.length - 1;
        int compTimes = 0;
        while (low <= high) {
            ++compTimes;
            int mid = (low + high) / 2;
            if (a[mid] == key){
                map.put(key, compTimes);
                return map;
            }else if (a[mid] > key){
                high = mid - 1;
            }else {
                low = mid + 1;
            }
        }
        return null;
    }
}

输出结果为：
2:5
4:5
6:5
8:5
10:5
12:5
14:5
16:5
18:5
20:5
22:5
24:5
26:5
28:5

30:5

二分查找的次数为logN,最多查找5次的话，那么N最大可以是31，最小可以是16，最多有31个数。规律应该是这样。

31个数经过5次查找成功的节点数为2^5-1=16

30个数经过5次查找成功的节点数为2^5-1-1=15

29个数经过5次查找成功的节点数为2^5-1-2=14

...

16个数经过5次查找成功的节点数为2^5-1-15=1

15个数经过5次查找成功的节点数为2^5-1-16=0

编辑于 2019-06-16 09:54:36 回复(4)