今天打开简书,看到又收获几个喜欢,感觉挺棒的。可是又看看上一篇还是上个月的事,真的惭愧,这个月换了工作,换了个环境,一切都是新的开始,正好今天清明节放假就再来写点东西吧,继续填坑。
- 使用场景:
经常有的困惑是,学了一堆算法,在具体刷题的时候不知道用什么方法。这里我来谈下二分的使用场景:
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.直接上题目
分析:怎么找一个逼近 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;
}