二分查找的经典样例

对于查找任务来说，通常就是寻找目标值或者目标区间出现的位置。而看到排序数组+查找，第一反应就是二分查找。以下问题都可以直接转化到这个问题上来。

• 34.在排序数组中查找元素的第一个和最后一个位置
  • 查找元素出现的第一个位置，等价于查找从这个数开始的区间。
  • 查找元素出现的最后一个位置，等价于查找以这个数结束的区间。
• 35.搜索插入位置
  • 查找元素的插入位置，等价于查找从这个数开始的区间。
• 69.x 的平方根
  • 查找x的平方根（向下取整），等价于查找从满足 a*a <= x 的最大整数 a 开始的区间。
• 367.有效的完全平方数
  • 判断完全平方数，等价于查找是否存在一个数满足 a*a == x。
  • 当然也可以变成查找从满足 a*a <= x 的最大整数 a 开始的区间，然后判断这个 a 是否满足 a*a == x。
• 704.二分查找
  • 标准的查找。
• 剑指 Offer 53 - I.在排序数组中查找数字 I
  • 等价于34，将两个区间的边界相减即可。

搞清楚这些问题的本质，就很容易解决了。