3.6.4　算法改进——使用二分查找第n个丑数

如果要从已知的范围内找到某个数字，我们可以采用二分查找算法来提高查找效率。对于本题来说，要借助二分查找来提高效率，需要先解决两个问题：

（1）查找的范围如何确定。

（2）如何确定某个数是第几个丑数。

问题1非常好解决，输入的3个数字a、b和c中的最小数就是我们要查找范围的最小边界，a、b和c中的最小数乘以n的值就是我们要查找范围的最大边界。

问题2也有一个很巧妙的方法可以解决，根据上面的定义，我们知道能够被a、b或c整除的数都被定义为丑数，因此对任意一个数X，我们只需要能够确定0～X范围内有多少个丑数即可，即找到0～X范围内所有可以被a整除或可以被b整除或可以被c整除的数。有以下7种场景：

（1）只能被a整除（X/a）。

（2）只能被b整除（X/b）。

（3）只能被c整除（X/c）。

（4）只能够被a和b整除（X/a_b）。

（5）只能够被a和c整除（X/a_c）。

（6）只能够被b和c整除（X/b_c）。

（7）能够被a、b和c整除（X/a_b_c）。

由于计算上述前3种场景的结果存在重复计算的情况，例如可以被a整除，也可以被b整除的数会被计算两次，因此我们需要把情况4、5、6计算出的结果剔除掉。同样，场景4、5、6也存在重复计算的情况，能同时被a、b和c整除的数被计算了两次，需要再用场景7进行修正。因此，计算0～X范围内有多少个丑数最终可以表示为如下表达式：

X/a + X/b +X/c – X/a_b – X/a_c – X/b_c + X/a_b_c

其中情况4、5、6、7中的除数计算最小公倍数即可得到。

编写代码如下：

需要注意，二分查找得到的结果并不是本题的最终结果，二分查找得到的是一个最接近答案的区间最大值，我们需要再处理一下，找到小于等于它的最近的丑数。