数据结构小记

二分搜索

作者 Wavy Peng 日期 2018-05-04
数据结构
数据结构小记

【声明】 图源：牛客网

应用场景

  • 在有序序列中查找一个数，时间复杂度O(logN)（经典场景）
    • 给定有序数组arr，判断m是否存在arr中
  • 并不一定非要在有序序列中才能得到应用

考察点

  • 边界条件（处理不当会发生死循环、漏掉某个数的情况），需要仔细设计对中间划分点的逻辑判断以及设计循环的终止条件
  • 给定处理或查找的对象不同（数组有无重复元素）
  • 判断条件不同
  • 要求返回的内容不同
  • 有序循环数组中进行二分搜索
    • 有序循环数组：有序数组左边任意长度的部分拿到右边去，右边部分拿到左边来形成的数组

注意点

  • $mid=(left+right)/2$，虽然是常见写法，但要注意当left和right下标值过大时，可能会导致溢出。因此更安全的写法应该是$mid=left+(right-left)/2$。

经典案例

案例一

题目

求局部最小值

给定一个无序数组arr，已知任意相邻的两个元素，值都不重复。请返回任意一个局部最小的位置。

所谓局部最小的位置是指，如果arr[0]<arr[1]，那么位置0就是一个局部最小的位置。如果arr[N-1]（也就是arr最右边的数）小于arr[N-2]，那么位置N-1也是局部最小的位置。如果位置i既不是最左位置也不是最右位置，那么只要满足arr[i]同时小于它左右两侧的值即（arr[i-1]和arr[i+1]），那么位置i也是一个局部最小的位置。

分析

二分搜索实现，时间复杂度O(logN)

  • arr为空或长度为0，返回-1，表示局部最小位置不存在

  • 如果arr长度为1，返回0，因为此时0是局部最小位置

  • 如果arr长度大于1，先检测两边的位置：

    • 如果arr[0]<arr[1]，直接返回0
    • 如果arr[N-1]<arr[N-2]，直接返回N-1
    • 如果上述两个条件不满足，则观察arr[mid]的情况：
      • 如果arr[mid]同时小于其左右两边的数，则mid就是一个局部最小位置，直接返回mid
      • 如果arr[mid]小于其右边的数，大于其左边的数，则从mid向左看整体趋势减小，此时mid左侧存在局部最小位置。此时对左边继续进行同样逻辑的二分搜索。
      • 如果arr[mid]大于其右边的数，小于其左边的数，则从mid向右看整体趋势减小，此时mid右侧存在局部最小位置。此时对右边继续进行同样逻辑的二分搜索。
      • 如果arr[mid]大于左右两边的数，则任选一边，继续进行同样逻辑的二分搜索。

考点

二分搜索并不一定要在有序的数组上才可进行，只要在查找的过程中能够淘汰一半，就可以使用

实现
public int getLessIndex(int[] arr) {
    int len = arr.length;
    if (len == 0) return -1;
    if (len == 1 || arr[0] < arr[1]) return 0;
    if (arr[len-1] < arr[len-2]) return len-1;

    int left=1,right=len-2,mid=0;
    while (left <= right) {
        mid = left+(right-left)/2;
        if (arr[mid+1] > arr[mid] && arr[mid-1] > arr[mid]) {
            return mid;
        }else if (arr[mid] > arr[mid-1]) {
            right = mid-1;
        }else if (arr[mid] > arr[mid+1]) {
            left = mid+1;
        }
    }
    return -1;
}

案例二

题目

元素最左出现

给定一个有序数组arr，再给定一个整数num，请在arr中找到num这个数出现的最左边的位置。

分析
  • 定义一个变量res记录最近一次找到目标值的下标位置。查找方式采用二分查找。

实现
public int findPos(int[] arr, int n, int num) {
    if(arr == null || n<=0)
        return -1;
    int res = -1;
    int left=0,right=n-1,mid=0;
    while(left<=right){
        mid = left+(right-left)/2;
        if(num==arr[mid]){
            res = mid;
            right = mid-1;
        }else if(num>arr[mid]){
            left=mid+1;
        }else{
            right=mid-1;
        }
    }
    return res;
}

案例三

题目

循环有序数组最小值

给定一个有序循环数组arr，返回arr中的最小值。有序循环数组是指，有序数组左边任意长度的部分放到右边去，右边的部分拿到左边来。比如数组[1,2,3,3,4]，是有序循环数组，[4,1,2,3,3]也是。

分析
  • 注意：当arr[L]=arr[M]=arr[R]时，只能通过遍历的方式进行查找。

实现
public int getMin(int[] arr, int n) {
    if(arr==null || n<=0)
        return -1;
    int left = 0,right = n-1,mid = 0;
    while(left<right){
        //当数组只有两个值的时候
        if(right-left==1)
            break;
        //左边小于右边，left到right范围内是有序的
        if(arr[left]<arr[right])
            return arr[left];
        mid=left+(right-left)/2;
        if(arr[left]>arr[mid]){//证明最小值在Left和mid之间
            right = mid;
            continue;
        }
        if(arr[right]<arr[mid]){//证明最小值在mid和right之间
            left=mid;
            continue;
        }
        //当出现等值的情况
        while (left<right){
            if (arr[left]==arr[mid]){
                left++;
            }else if (arr[left]<arr[mid]){
                return arr[left];
            }else {
                right=mid;
                break;
            }
        }
    }
    return Math.min(arr[left],arr[right]);
}

案例四

题目

最左原位

给定一个有序数组arr，其中不含有重复元素，请找到满足arr[i]==i条件的最左的位置，如果所有位置上的数都不满足条件，返回-1.

分析
  • 定义res，记录最后一次发生arr[i]==i的位置
  • 如果arr[0]>N-1，则arr[0]~arr[N-1]上的位置均大于N-1，返回-1
  • 如果arr[N-1]<0，则arr[0]~arr[N-1]上的位置均小于0，返回-1
  • 考虑位置M，如果arr[M]>M，在0~M-1的范围上继续二分查找；如果arr[M]<M，在M+1~N的范围上继续二分查找；如果arr[M]==M，用res记录当前的M值，之后再从0~M-1的范围继续二分搜索

实现
public int findPos(int[] arr, int n) {
    // write code here
    if(arr == null || n<=0)
        return -1;
    int res = -1;
    if(arr[0]>n-1 || arr[n-1]<0)
        return -1;
    int left = 0,right = n-1;
    int mid = 0;
    while(left<=right){  // 二分查找目标值
        mid = left+(right-left)/2;
        if(arr[mid]==mid){
            res = mid;
            right = mid-1;
        }else if(arr[mid]>mid){ // 0~mid-1
            right = mid-1;
        }else{  // mid+1~n-1
            left = mid+1;
        }
    }
    return res;
}

案例五

题目

完全二叉树计数

给定一棵完全二叉树的头节点head，返回这棵树的节点个数，如果完全二叉树的节点数为N，请实现时间复杂度低于O(N)的解法。

分析
  • 普通遍历方式，时间复杂度O(N)。
  • 最优解，时间复杂度O(logH^2)，H是二叉树的高度。实质上是利用二分来确定右子树的最左节点的位置
    • 首先找到二叉树最左的节点，统计完全二叉树的高度。
    • 找到二叉树右子树的最左节点，如果头节点右子树的最左节点能到达最后一层，说明头节点左子树一定是一棵满二叉树，可以根据公式计算满二叉树的节点个数，再加上头节点。之后利用递归的方式求解右子树的节点个数。
    • 如果头节点右子树的最左节点不能到达最后一层，说明头节点的右子树是一棵满二叉树，不过比左子树少一层，可以根据公式计算满二叉树的节点个数，再加上头节点。之后利用递归的方式求解左子树的节点个数。

实现
class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
public class CountNodes {
    public int count(TreeNode root) {
        // write code here
        if(root == null){
            return 0;
        }
        int res = 0;
        int left = getDepth(root.left);//左子树高度
        int right = getDepth(root.right);//右子树高度
        if(left == right){
            res += (int) (Math.pow(2, left)-1 +1);//计算左子树加根
            res += count(root.right);//计算右子树
        }else if(left > right){
            res += (int) (Math.pow(2, right)-1 +1);//(满树)计算右子树加根
            res += count(root.left);//计算左子树
        }
        return res;
    }
     
    // 获取树的深度
    public int getDepth(TreeNode root){
        int depth = 0;
        while(root!=null){
            depth++;
            root = root.left;
        }
        return depth;
    }
}

案例六

题目

快速N次方

如何更快的求一个整数k的N次方。如果两个整数相乘并得到结果的时间复杂度为O(1)，得到整数k的N次方的过程请实现时间复杂度为O(logN)的方法。

分析
  • 普通方法，时间复杂度O(N)

  • 二分查找，时间复杂度O(logN)

实现
public int getPower(int k, int N) {
    if(N==0)
        return 1;
    long sum = 1;
    long tmp = k;
    int mod = 1000000007;
    while(N!=0){
        if((N&1)!=0) // 判断奇数
            sum=(sum*tmp)%mod;
        tmp = (tmp*tmp)%mod;
        sum = sum%mod;
        N=N>>1;
    }
    return (int)sum;
}
扩展

为什么要对1000000007取模？

其实不止1e9+7，还有1e9+9和998244353。这三个数都是一个质数，同时小于$2^{30}$

  • 所有模过之后的数在加法操作在int范围内不会溢出，即$a,b<2^{30}, a+b<2^{31}$
  • 在乘法操作后在long long范围内不会溢出，即$ab<2^{60}$
  • 对于$[1,p)$中的整数，可进行mod P乘法群意义下的除法，即可以使用扩展欧几里得算法求得$gcd(x,P)=ax+bP+1$中的a。
FEATURED TAGS
数据结构