金衡数据 · 学习练习
从快递柜找号码，理解二分查找
大学计算机练习：按闭区间边界与向下取整规则选取中点。包含主问题、四层提示、答案、图解与一道举一反三练习，可按自己的节奏完整阅读。
大学计算机
先尝试回答主问题，再逐层阅读提示并核对答案。完成后，用举一反三检验方法能否用于另一组条件。学段仅供选题参考。
主问题：读条件，找方法
问题
快递柜的取件编号已按从小到大排列且互不重复，位置从1开始计数。目前候选范围是第 1 项到第 16 项，左右端点都包含。二分查找规定中间位置取 (左端点+右端点)÷2 后向下取整。第一轮应比较第几项？
四层提示
- 第0层 零基础救生圈
二分查找先找候选范围的中间位置。题目规定位置从1开始，两个端点相加后除以2，再向下取整。
- 第1层 生活场景建模
想象一排按顺序排好的快递柜，先找到这排的中间一格；如果中间夹在两格之间，按题目规则选靠左的那格。
- 第2层 防坑雷达
题目问的是第几项的位置，不是柜子上写的取件号码；不要从0开始数，也不要把小数往上取整。
- 第3层 解题实操
第一步：把左右位置相加再除以2：（1＋16）÷2＝8.5。 第二步：按题目规定向下取整，得到8。 第三步：因此第一轮比较第8项。
答案与核对
8项
举一反三：换一组条件再试
问题
一个升序且元素互不相同的数组有 13 个元素，下标从 0 到 12。二分查找当前候选闭区间为 [0,R]，R 是 0 到 12 的整数。若按 m=⌊(L+R)/2⌋ 取中点，已知中点 m=4，R 可能是哪几个整数？请列出全部可能。
四层提示
- 第0层 零基础救生圈
向下取整等于 4，表示原数大于或等于 4，且小于 5。
- 第1层 生活场景建模
像在尺子上找一个位置：只要原位置落在从 4 到不到 5 的范围里，向下取整都会得到 4。
- 第2层 防坑雷达
4 是取整后的中点下标，不代表右端点只能是 8；必须把所有可能整数都找出来。
- 第3层 解题实操
第一步：L=0，⌊R/2⌋=4，故 4≤R/2<5。第二步：两边同乘 2 得 8≤R<10。第三步：R 为整数，只有 8、9。代回验证 ⌊8/2⌋=4、⌊9/2⌋=4。
答案与核对
R 可以是 8 或 9。