今天打开简书，看到又收获几个喜欢，感觉挺棒的。可是又看看上一篇还是上个月的事，真的惭愧，这个月换了工作，换了个环境，一切都是新的开始，正好今天清明节放假就再来写点东西吧，继续填坑。
- 使用场景：
经常有的困惑是，学了一堆算法，在具体刷题的时候不知道用什么方法。这里我来谈下二分的使用场景：
When
你需要优化一个 O(N) 的暴力算法到更快的算法 ，为什么这么说呢？因为比 O(N) 更快的算法无非就是 O(1) 和 O(logN) ，O(1)的太少了，剩下的只有 O(logN) ，那这个复杂度的算法有哪些呢？二分法和倍增法（反向二分，很少这类题）。比如，你在面试让你优化一个 O(N) 的算法（在一个数组中用 for 循环找一个 target），这是面试官可能要说，能不能比 O(N) 更好呢？这个时候有两种方案，一种是从系数优化，无非就是少一点操作，还有就是从复杂度优化，就只能到 O(logN) ，就基本只有二分算法。
在题目中看到 Sorted Array or Rotated Sorted Array 这些关键字，就可以考虑二分了，因为二分的使用条件就是有序的排列数组。
How
找到满足某个条件的 第一个或者最后一个位置。
2.直接上题目
QQ截图20160402000152.jpg
分析：怎么找一个逼近 X 的平方根呢？ 相当于找一个数 K 的平方是小于 X 的最大的树，也就可以理解成找最后一个位置的数字，它的平方小于等于 X（Last number that number^2 <= X）.这种一般辅助画图都能很好的解决。
值得注意一点的是，这种找 last position 和 first position 对于等于的处理。找 first position 是把 end 移到 mid，而 last position 是把 start移到 mid。
+ (NSInteger)sqrt:(NSInteger)x {
NSInteger start = 0;
NSInteger end = x;
while (start + 1 < end) {
NSInteger mid = start + (end - start) / 2;
if (mid * mid <= x) {
start = mid;
} else {
end = mid;
}
}
if (end * end <= x) { // 找最大的，先比较 end
return end;
}
return start;
}
