二分查找
https://blog.csdn.net/silence723/article/details/52043670/
https://www.1point3acres.com/bbs/thread-432793-1-1.html
https://leetcode.com/articles/introduction-to-binary-search/
递增还是递减,没重复元素吧?
里面把重点写出来了,我感觉主要是理解这三种模板的不同
- start, end
- loop condition, start <=end, start < end, start + 1 < end
- move start or end, this is the key, if array have duplicate number, how to move? 这个如果不理解就很难应用好
4 process the left elements.
qucik select ,find peak
先升序后降序,二分查找?分治?
leetcode 33
脉脉二分山峰值,画下图就知道和lee33类似,
二分
微软面试的一道二分题,只是后来用了一下。。
当提出一个函数写的时候参数少了弄错了,,
递归,迭代方法都写下
Example:
Input: [1,null,2,3]
1
2
/
3
Output: [1,3,2]
template1
注意点:
- 开闭区间
- mid防止溢出,除法加速
- 先判断不等最后判断等,等的情况少一点,
- 找不到的情况left和right最后的值?
- 时间复杂度怎么算的?
- 为什么left = right?
- 加()>>运算符优先级了解下。。
1 | class Solution { |
2.iterative solution
1 | /** |
- 本文作者: John Doe
- 本文链接: http://example.com/2019/01/10/algorithm/search/
- 版权声明: 本博客所有文章除特别声明外,均采用 MIT 许可协议。转载请注明出处!