Js算法与数据结构拾萃（5）：二分法

从本节开始，重心将放到算法层面。

也许你在《幸运52》看过这样的游戏，假设一台iPhone x 标价8300元，某人让你尽可能快地猜出它的价格。

•10k——贵了•5k——便宜了•再猜：（10+5）/2=7.5k——便宜了•（10+7.5）/2=8.75k——贵了•....

经过有限的几次猜测，你很快猜出了它的真实价格。

采用二分法查找时，数据需是排好序的。主要思想是：（设查找的数组区间为array[s, e]）

（1）确定该区间的中间位置m

（2）将查找的值T与array[m]比较,若相等，查找成功返回此位置；否则确定新的查找区域，继续二分查找。区域确定如下：

•这里设array从小到大排列,•array[m]>T由数组的有序性可知array[m,……,e]>T;•故新的区间为array[s,……，m-1],•类似上面查找区间array[s,……，m-1]。•每一次查找与中间值比较，判断是否查找成功，不成功当前查找区间缩小一半，循环查找，即可。•时间复杂度:O(log2n)。

案例1 Guess Number Higher or Lower（猜数字）

对应leetcode 374题 难度：简单 https://leetcode.com/problems/guess-number-higher-or-lower/

We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I'll tell you whether the number is higher or lower.

You call a pre-defined API guess(int num) which returns 3 possible results (-1, 1, or 0):

-1 : My number is lower
 1 : My number is higher
 0 : Congrats! You got it!

Example :

Input: n = 10, pick = 6
Output: 6

题解

你可以用一个循环来处理它。复杂度为O(n)。肯定是超时的。应该考虑二分法。

此题的解法无JavaScript可选。硬着头皮用java写的解法是：

/* The guess API is defined in the parent class GuessGame.
   @param num, your guess
   @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
      int guess(int num); */

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        long l = 1, r=n;
        int res;
        while((res = guess((int)((l+r)/2))) != 0){
            if(-1 == res){
                r = (l+r)/2-1;
            }else if(1 == res){
                l = (l+r)/2+1;
            }          
        }
        return (int)((l+r)/2);
    }
}

复杂度为:O(log2n)

案例2：leftpad

2016年前端界发生了这么一件事：

最近 NPM 圈发生了“一个 17 行的模块引发的血案”。left-pad[1] 工具模块被作者从 NPM 上撤下，所有直接或者间接依赖这个模块的 NPM 包就忧伤的挂掉了，包括 babel 这样的热门项目。 而其中的原因大概是这样：作者 Azer 写了一个叫 kik[2] 的工具和某个公司同名了，这天公司的律师要求其删掉这个模块，把 kik 这个名字“让”给他们，作者不答应，律师就直接找 NPM 了，而 NPM 未经作者同意就把包的权限转移给了这家公司。于是，Azer 一怒冲冠，将他所有的 NPM 包全部删掉了。 ——《从 left-pad 事件我们可以学到什么[3]》

于是就有好事者研究此模块，发现它的作用是在字符串前padding一些东西到一定的长度。

他是这么写的：

module.exports = leftpad;

function leftpad (str, len) {
  var i = -1;
  len = len - str.length;

  while (++i < len) {
    str = ' ' + str;
  }

  return str;
}

使用方法：

// 补齐n个0 拼接n次
console.log(leftpad('',10,‘0’)) // 000...共n个0...0

好事者批评说，这种代码写的太烂了。

确实，笔者简单测试发现，在noodejs环境下，当n去到1000w次时，该模块运行时间为1600-1800ms左右。于是网上就开始了各种秀写法的表演。

优化思路（二分法）

你至今可以在GitHub上，看到这个小小的模块写法的各种实现历史，但本文只提及二分法的解答。

作为非0自然数，无非奇数或偶数==>也就是说，所有自然数都可以用这样一个集合表示

N={n|n=2x+C,x ∈ N, C ∈ {0,1}}

我们用一个total来缓存，在while循环中，有一个变量来缓存这个迭代产生的附加字符串ch：

设 需要增加m个ch

// 旧方法
循环第1次：增加1个ch
循环第2次：增加2个ch
循环第3次：增加3个ch
...
循环第m次，增加m个ch

// 新方法
循环第1次：增加至少1个ch
循环第2次：增加至少2个ch
循环第3次：增加至少4个ch
。。。
循环n次，增加至少2^n个ch

那么，对于任何非0自然数，只要经过n=log2m次二分法迭代循环，就可以快速地完成需求。

当m=10000000 （1000万）时，旧方法至多需要迭代1000万次，而旧方法至多迭代8次。

题解

function leftpad2(str, len, ch) {

  let _len=len-str.length;
  let total = ''
  while (_len) {
    // 当遇到奇数时，也就是
    if (_len % 2 == 1) {
      total += ch
    }

    if (_len == 1) {
      return total + str
    }

    ch += ch // 0 00  0000
    _len = parseInt(_len / 2)
  }

}

node下同时测试1000万次，str='';ch=0：

•lefpad：1727ms•Laftpad2：1ms

进一步理解：位运算

上面的代码虽然简单，但理解起来还是有点难度。

二分法是和二进制高度相关的，我们知道所有数字都可以用二进制表示。我们回想下十进制转二进制的算法思想：

这里涉及几个js中罕见的运算：

按位与（&）

给定两个数，对它们32 位表达式的每一个位执行按位“与（&&）”运算。如果两个位均为 1，则结果是 1。否则，结果为 0。得到的结果拼合起来转为对应的数。

按数位进行与的运算（&&），

比如计算 9 & 5

// 9 二进制是 1001，补足32位为 00000000000000000000000000001001
var expr1 = 9;

// 5 是 00000000000000000000000000000101
var expr2 = 5;

/*
00000000000000000000000000001001 & 
00000000000000000000000000000101=
00000000000000000000000000000001= 
1
*/

var result = expr1 & expr2; // 弹出【1】

同理还有按位或，按位亦或等。

留意到：1的二进制32位表达式为

00000000000000000000000000000001

假设一个数m，它的二进制32位表达式最后一位非1（奇数）即0（偶数），与1进行按位与运算，偶数为0，奇数为1.

按位与 在本例的价值在于：一个数，按位与1 不为0，表示它就是奇数。

左移和右移（>>和<<）

给定一个数N，转为二进制之后，移动n位。假设N转化为二进制后的数N2=>

如果是左移（N << n）,N2左移动n位后补0，如果溢出32位范围则舍弃

如果是右移（N >> n），N2右移动n位，溢出部分舍弃。演算式如下：

从演算中可以看出，左移动1位就是乘以2，左移2位就是乘以4。反之就是做除法。2位有限推论：也就是说，你可以理解为，在10进制中：

•*m左移动n位 ：代表 m 除以 2n后，得到的结果 的整数部分 *•m右移n位意味着 m 乘以 2n

好了，回到leftpad1231，我们可以给出更好的优化方案：

function leftpad3(str, len, ch) {
  let _len = len - str.length
  let total = ''
  while (_len) {
    if (_len & 1) {
      total += ch
    }

    if (_len == 1) {
      return total + str
    }

    ch += ch // 00  0000
    _len = _len >> 1
  }
}

这样算法的速度可以再提升一点点。因为两个算法复杂度是一致的。我们写个自动测试方法再提升一下计算量：

// 测试程序
const test=(fn,msg)=>{
  const startTime = new Date().getTime()
  const N=10000000 // 1000万
  const str=''
  const ch='0'
  for(let i=0;i<N;i++){
    fn(str, i, ch)
  }
  const endTime = new Date().getTime()
  console.log(msg,endTime-startTime)
}

test(leftpad2,'leftpad2运行用时') //
test(leftpad3,'leftpad3运行用时')

在node环境下运行结果：

计算性能差了一倍左右。

案例3：Pow(x,n)（计算x的n次幂）

对应leetcode第50题 https://leetcode.com/problems/powx-n/

如题，不使用Math.pow(x,n)，计算x的n次幂。(n为整数)

Implement pow(x, n)[4], which calculates x raised to the power n (xn).

Example 1:

Input: 2.00000, 10
Output: 1024.00000

Example 2:

Input: 2.10000, 3
Output: 9.26100

Example 3:

Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25

Note:

•-100.0 < x < 100.0•n is a 32-bit signed integer, within the range [−231, 231 − 1]

题解

任何一个数

回忆下高中数学幂运算：如果令 a1 = n/2：

xn = xa1 * xa1 = xa1 + a1

如果令 a2 = n / 22：

xn = xa2 * xa2 * xa2 * xa2 = xa2 + a2 + a2 +a2

...

如果令 am = n / 2m，则有：

xn = xam * ...( m-2 个 ) * xa2 = x2^m * am =( xam )2^m

当m无限大时，am -> 0。

因此，我们假设要做2m次循环，用一个total来累计计算的结果。

var myPow = function(x, n) {
  if (n < 0) {
    x = 1 / x
  }
  let res = 1
  let total = x
  while (n) {
    if (n & 1) {
      res *= total
    }
    total *= total
    n /= 2
  }
  return res
}

变化图：递归

类似的，你也可以用递归：

var myPow = function(x, n) {
        if (n == 0) return 1;
        if (n < 0) return 1 / myPow(x, -n);
        let mid = myPow(x, n / 2);
        if (n & 1) return mid * mid * x;
        return mid * mid;
};

References

[1] left-pad: https://github.com/azer/left-pad/blob/master/index.js [2] kik: https://github.com/starters/kik [3] 从 left-pad 事件我们可以学到什么: https://segmentfault.com/a/1190000004700432 [4] pow(x, n): http://www.cplusplus.com/reference/valarray/pow/