一、理论
适用二分查找的条件：1. 单调递增或递减 ； 2. 存在上下界； 3.能够通过索引访问（数组）
Tips：题目中看见 数组 + 有序，要第一时间想到 二分 ！！！
【循环不变量】的设计：声明的 left 和 right 的意义不同，二分查找的边界就不同，因此需要理解 left 和 right 的定义，并在循环中始终维护。见下面示例代码~
示例代码1（前闭后闭）：
有个BUG忘改了， int mid = l + (r - l) / 2;
示例代码2：（前闭后开）
二、典型例题
①：实现一个求解平方根的函数（LC69）
方法1：二分法
方法2：牛顿迭代法（了解）
class Solution { public int mySqrt(int x) { if (x == 0 || x == 1) return x; int start = 0; int end = x; while (start <= end){ // 循环结束条件带等号 int mid = start + ((end - start) >> 1); if (mid > x / mid){ // 如果是 mid * mid > x 会出现int溢出 end = mid - 1; }else if (mid < x / mid){ start = mid + 1; }else { return mid; } } // 关于最后return的理解： // 最后一次循环时，start = end，那么计算后mid = start = end。 // while结束时start>end, 可以是end = mid - 1; 也可以是start = mid + 1; // 如果执行end = mid - 1，那么条件是 mid*mid > x // 如果执行start = mid + 1，那么条件是 mid*mid < x // 也就是要返回start和end中，较小的那个，也就是end return end; // return start - 1; } }