0%

T033、T081 二分查找、旋转数组

  • 一般二分、斐波那契分、两边都不管mi的写法
  • 旋转数组:模拟

二分查找(以单调递增为例)

初版

原理

  • e < x: 则e若存在必属于左侧子区间,故可(减除\(s [ mi,hi )\)并)递归深入\(s[lo,mi)\)
  • x < e: 则e若存在必属于右侧子区间,亦可(减除\(s [ lo,mi ]\)并)递归深入\(s(mi,hi)\)
  • e = x: 已在此处命中,可随即返回 #### 代码
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    template <typename T>
    static Rank binarySearchA(T *S, const T a, Rank lo, Rank hi)
    {
    while (lo < hi)
    {
    Rank mi = (lo + hi) >> 1;
    if (a < S[mi]) hi = mi;
    else if (S[mi] < a) lo = mi;
    else return mi;
    }
    return -1;
    }

优化1:斐波那契查找

原理

  • 原版中,转向左、右分支前的关键码比较次数不等(左一次,右两次)
  • 宁愿左边多递归几层来平衡一下
  • 若有 \(n = fib(k)-1\),则可取 \(mi = fib(k-1)-1\),前、后子向量的长度分别为 \(fib(k-1)-1\)\(fib(k-2)-1\) #### 代码
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    template <typename T>
    static Rank fibSearch(T *S, const T a, Rank lo, Rank hi)
    {
    for (Fib fib(hi - lo); lo < hi;)
    {
    // Rank mi = (lo + hi) >> 1;
    while (hi - lo < fib.get()) fib.prev();
    Rank mi = lo + fib.get() - 1; // 找到合适的轴点

    if (a < S[mi]) hi = mi;
    else if (S[mi] < a) lo = mi;
    else return mi;
    }
    return -1;
    }

优化2:两分支的二分查找

原理

  • 原版中,转向左、右分支前的关键码比较次数不等(左一次,右两次)
  • 如果直接只比较一次,就没有这个问题了
  • e < x: 则e若存在必属于左侧子区间s[1o, mi),故可递归深入
  • x <= e: 则e若存在必属于右侧子区间s[mi, hi),亦可递归深入
  • 直到hi - lo = 1,才判断是否命中 ##### 代码
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    template <typename T>
    static Rank binarySearchB(T *S, const T a, Rank lo, Rank hi)
    {
    while (1 < hi - lo)
    {
    Rank mi = (lo + hi) >> 1;
    a < S[mi] ? hi = mi : lo = mi;
    }
    return a == S[lo] ? lo : -1;
    }

优化3:两边都嫌弃mi的两分支二分查找

原理

  • 转入右侧子向量时,左边界取mi+1(而非mi) #### 代码
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    template <typename T>
    static Rank binarySearchC(T *S, const T a, Rank lo, Rank hi)
    {
    while (hi < lo)
    {
    Rank mi = (lo + hi) >> 1;
    a < S[mi] ? hi = mi : lo = mi + 1;
    }
    return lo - 1;
    }
    #### 问题
  1. 两边都不要mi,那如果mi命中了怎么办? 答:mi如果命中,那后边的查找都是白忙活,本质就是等结束。但是在白忙活的过程中,lo是不会变的,因为每次查找都会发现target小了,得在左侧子向量找。这样,lo就被保留下来了。最后返回的lo-1不就是刚开始的mi吗,没毛病。

  2. 那mi没有命中怎么办?(指target比mi大而比mi+1小),这样返回mi没问题吗? 答:没问题。须知,查找的语义约定为:查找e,返回不大于e且秩最大的元素。这种写法是符合语义约定的,之前的各种失败返回-1的算法反而不符合。

二分·旋转数组

  • 旋转数组:升序向量,截取前边一段接到后边 ## T31 旋转向量元素不重复

T81 旋转向量元素可重复

T153

看到这里的姐妹一看就要暴富暴美,为什么不让这一天提前一点呢ヾ(≧▽≦*)o