参考答案及解析

题目1：基本二分查找

判断题

1. √
2. ×
3. √

选择题 4. B 5. C

题目2：查找第一个大于等于目标值的位置

判断题

1. √
2. √
3. √

选择题 4. A 5. B

题目3：在旋转有序数组中查找目标值

判断题

1. √
2. √
3. √

选择题 4. C 5. B

题目4：二分答案-求平方根

判断题

1. √
2. √
3. √

选择题 4. B 5. B

题目5：二分答案-最大值最小化问题

判断题

1. √
2. √
3. √

选择题 4. B 5. A

二分查找专题总结

二分查找是一种高效的查找算法，时间复杂度为O(log n)，但要求数据必须有序。二分答案则是二分查找思想的延伸，用于解决最优化问题。

关键知识点：

1. 基本二分查找模板：

   • 循环条件：while (left <= right)
   • 中间值计算：mid = left + (right - left) / 2
   • 调整边界：根据比较结果调整left或right

2. 二分查找变种：

   • 查找第一个等于目标值的位置
   • 查找最后一个等于目标值的位置
   • 查找第一个大于等于目标值的位置
   • 查找最后一个小于等于目标值的位置

3. 二分答案应用场景：

   • 求平方根、立方根等
   • 最大值最小化问题
   • 最小值最大化问题
   • 可行性判断问题

4. 注意事项：

   • 确保数据有序（或具有单调性）
   • 注意整数溢出问题
   • 正确处理边界条件
   • 理解循环不变量的概念