牛客网《BAT面试算法精品课》视频链接：《BAT面试算法精品课》 笔记链接： 牛客网《BAT面试算法精品课》笔记一：排序 牛客网《BAT面试算法精品课》笔记二：字符串 牛客网《BAT面试算法精品课》笔记三：队列和栈 牛客网《BAT面试算法精品课》笔记四：链表 牛客网《BAT面试算法精品课》笔记五：二分搜索 牛客网《BAT面试算法精品课》笔记六：二叉树 牛客网《BAT面试算法精品课》笔记七：位运算 牛客网《BAT面试算法精品课》笔记八：排列组合 牛客网《BAT面试算法精品课》笔记九：概率 牛客网《BAT面试算法精品课》笔记十：大数据 牛客网《BAT面试算法精品课》笔记十一：动态规划 二分搜索常见应用场景： 1.在有序序列中查找一个数，时间复杂度O(logN) 2.并不一定在有序序列中才能得到应用 二分搜索常见考察点： 1.对于边界条件的考察以及代码实现的能力 2.二分搜索题目变化很多 01.给定处理或查找的对象不同 02.判断条件不同 03.要求返回的内容不同 二分搜索的重要提醒： Mid=(left+right)/2，获取中间值经常这样写，但是要注意当right很大的时候，(left+right)会溢出，所以更安全的写法是mid=left+(right-left)/2 常见题型： 案例1. [](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042139.png) 本题依然可以用二分搜索来实现，时间复杂度为O(logN)，此题说明了二分搜索并不一定要在有序才能进行[](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042140.png) **案例2.** 给定一个有序数组arr，再给定一个整数num，请在arr中找到num这个数出现的最左边的位置。 Num=3，全局变量res=-1，res记录最后找到3的位置 1 2 3 3 3 3 4 4 4 4 4 4 4 4 4 1 2 3 3 3 3 4 1 2 3 3 **案例3.** 给定一个有序循环数组arr，返回arr中的最小值。有序循环数组是指，有序数组左边任意长度的部分放到右边去，右边的部分拿到左边来。比如数组[1,2,3,3,4]，是有序循环数组，[4，1，2，3，3]也是。 如果arr[L]<arr[R]，那么最小值就是arr[L][](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042141.png) 如果arr[L]>=arr[R]，arr[L]>arr[M]，说明最小值在L到M的范围上[](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042142.png) 如果arr[L]>=arr[R]，arr[M]>arr[R]，说明最小值在M到R的范围上 [](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042143.png) 如果arr[L]>=arr[R]，arr[L]<=arr[M]，arr[M]<=arr[R],说明arr[L]，arr[R]，arr[M]三值相等，这种情况无法用二分来继续后续的查找过程 比如数组：2 2 … … 2 1 2 … … 2 2 此时1无论在哪个地方都满足本题的条件，所以此时就应该用遍历的方法。 **案例4.** 给定一个有序数组arr，其中不含有重复元素，请找到满足arr[i]==i条件的最左的位置。如果所有位置上的数都不满足条件，返回-1。 定义全局变量res记录最后一次发生arr[i]==i这种情况的位置，初始值res=-1 如果arr[0]>N-1或者arr[N-1]<0，那直接返回-1 中间值M，如果arr[M]>M，所以范围在0到M这，然后继续二分 如果arr[M]<M，所以范围在M+1到N-1这，然后继续二分 如果arr[M]=M，res=M，因为我们要找最左边的位置，所以继续在0到M-1的范围上进行二分搜索。 **案例5.** 给定一颗完全二叉树的头结点head，返回这棵树的结点个数。如果完全二叉树的节点数为N，请实现时间复杂度低于O(N)的解法。 先找到左子树最深的节点，获得深度为4，然后找到二叉树头节点的右子树的最左节点，如果深度也为4，说明这颗二叉树左子树是满二叉树，可由公式计算出节点数。此时右子树可以使用这种方式递归求出节点数。[](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042144.png) 如果头结点的右子树的最左节点不能到达最后一层，这说明头节点的右子树一定是一颗满二叉树，使用公式求得结点个数，左子树可以使用递归求出节点数。 [](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042145.png) 如果使用遍历的方式，时间复杂度为O(N) 而我们的最优解时间复杂度仅为O(logN2) **案例6.** 如何更快的求一个整数的N次方，如果两个整数相乘并得到结果的时间复杂度为O(1)，得到证书k的N次方的过程请实现时间复杂度为O(logN)的方法[](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042146.png)
牛客网《BAT面试算法精品课》笔记五：二分搜索
](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042139-300x121.png)](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042139.png) 本题依然可以用二分搜索来实现，时间复杂度为O(logN)，此题说明了二分搜索并不一定要在有序才能进行[](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042140.png) **案例2.** 给定一个有序数组arr，再给定一个整数num，请在arr中找到num这个数出现的最左边的位置。 Num=3，全局变量res=-1，res记录最后找到3的位置 1 2 3 3 3 3 4 4 4 4 4 4 4 4 4 1 2 3 3 3 3 4 1 2 3 3 **案例3.** 给定一个有序循环数组arr，返回arr中的最小值。有序循环数组是指，有序数组左边任意长度的部分放到右边去，右边的部分拿到左边来。比如数组[1,2,3,3,4]，是有序循环数组，[4，1，2，3，3]也是。 如果arr[L]=arr[R]，arr[L]>arr[M]，说明最小值在L到M的范围上[](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042142.png) 如果arr[L]>=arr[R]，arr[M]>arr[R]，说明最小值在M到R的范围上 [](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042143.png) 如果arr[L]>=arr[R]，arr[L]<=arr[M]，arr[M]<=arr[R],说明arr[L]，arr[R]，arr[M]三值相等，这种情况无法用二分来继续后续的查找过程 比如数组：2 2 … … 2 1 2 … … 2 2 此时1无论在哪个地方都满足本题的条件，所以此时就应该用遍历的方法。 **案例4.** 给定一个有序数组arr，其中不含有重复元素，请找到满足arr[i]==i条件的最左的位置。如果所有位置上的数都不满足条件，返回-1。 定义全局变量res记录最后一次发生arr[i]==i这种情况的位置，初始值res=-1 如果arr[0]>N-1或者arr[N-1]<0，那直接返回-1 中间值M，如果arr[M]>M，所以范围在0到M这，然后继续二分 如果arr[M]
Last updated:
{title}