上期题目测试答案

第一题：

可以看出这和我最开始举得例子基本一致

第一次 我们的 l=0 r=12，所以 mid=(l+r)/2=6 ，此时 mid 下标对应的元素是 31 小于 48 所以我们令 l=mid+1

第二次 我们的 l=7 r=12，所以 mid=(l+r)/2=9，此时 mid 下标对应的元素是 45 小于 48 所以我们令 l=mid+1

第三次我们的 l=10 r=12，所以 mid=(l+r)/2=11，此时 mid 下标对应的元素是 49 大于 48 所以我们令 r=mid-1

第四次我们的 l=10 r=10，所以 mid=(l+r)/2=10，此时 mid 下标对应的元素是 48 即我们需要的元素

自此我们找到元素 48 共经过四次比较

第二题与第一题基本一样 所以不在赘述

第三题：

因为二分查找的时间复杂度是 l o g 2 N log_2^Nlog2N​，所以此题的答案就是 l o g 2 128 log_2 128log2​128 等于 7

注意：如果 l o g 2 N log_2^Nlog2N​的结果不是整数 则向下取整+1

什么是冒泡排序

冒泡排序是一种排序算法与相邻元素比较 然后交换 因为每一趟的最大/最小值 最终会排序到当前趟的最后位置 所以形象的称为冒泡排序，是排序算法中比较基础的一种，这就意味着我们必须掌握。

算法原理

对本数列 {5,2,7,4,1,3,8,9} 进行冒泡排序 顺序从小到大

第一趟

2 5 4 1 3 7 8 9，比较了 7 次，确定了 9 是当前趟最后位

第二趟

2 4 1 3 5 7 8 9，比较了 6 次，确定了 8 是当前趟最后位

第三趟

2 1 3 4 5 7 8 9，比较了 5 次，确定了 7 是当前趟最后位

第四趟

1 2 3 4 5 7 8 9，比较了 4 次，确定了 5 是当前趟最后位

第五趟

1 2 3 4 5 7 8 9，比较了 3 次，确定了 4 是当前趟最后位

第六趟

1 2 3 4 5 7 8 9，比较了 2 次，确定了 3 是当前趟最后位

第七趟

1 2 3 4 5 7 8 9，比较了 1 次，确定了 2 是当前趟最后位

完成排序

第一：我们发现了 8 个元素 需要 7 趟排序。

第二：我们发现了 每趟排序只需要比较当前趟没有确定的元素 确定的元素无需比较，即每趟只需比较 元素个数-当前趟数 例如第三趟我们只需要比较 8-3 次 因为前两趟已经确定两个值 我们只需要在剩下六个中比较五次 就可以确定第三趟的极值。

第三：我们发现了第四趟就已经排序完成了，但仍然又比较了三趟，这是我们的优化点之一，优化趟数。

第四：我们发现了每趟的次数也可以优化，例如第二趟我们比较了六次，但其实在第一趟比较时就已经确定了 7 8 9 三个最大值，所以我们其实只用比较剩下 5 个元素，也就是只需要比较四次，因为我们每趟的次数也减少，所以我们最终的趟数也会随之减少。