二分搜索和一些用到二分思想的题目

前言

二分搜索可以说是应用非常广泛的一类算法了，非常多的暴力算法优化方案都是在一些条件下用二分，并且二分效率很高，可以让$\mathcal{O}(N)$算法秒变$\mathcal{O}(log_2N)$，效率大大提高(超时就先往二分上靠再说)，故本篇文章就讨论一下二分算法和一些关于二分的题目。

二分搜索

最基础的版本，用于在一个有序序列中查找需要的元素：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * 在一个列表中二分查找到某个值
 * @author xmmmmmovo
 * @date 2020/7/28 11:46
 * @param list 列表
 * @param key 需要查找的值
 * @param lo 左范围 默认为0
 * @param hi 右范围 默认为list.size - 1
 * @return 查找到了就返回下标，没查找到就返回-1
 * @since version-1.0
 */
fun <T : Comparable<T>> binarySearch(
    list: List<T>, key: T, _lo: Int = 0, _hi: Int = list.size - 1
): Int {

    var lo = _lo
    var hi = _hi

    while (lo <= hi) {
        val mid = lo + (hi - lo) / 2
        when {
            key < list[mid] -> {
                hi = mid - 1
            }
            key > list[mid] -> {
                lo = mid + 1
            }
            else -> {
                return mid
            }
        }
    }

    return -1
}

因为每一次都会是比上一次缩减1/2的搜查量，$\cfrac{N}{2^k} = 1$，所以时间复杂度为
$$
\mathcal{O}(\log_2N)
$$
空间复杂度为
$$
\mathcal{O}(1)
$$

查找列表中是否存在某元素

查找列表中是否存在某元素，这个问题，其实用遍历或者二分都可以解，并且不会特别影响时间复杂度，因为排序算法时间复杂度$\mathcal{O}(Nlog_2N)$已经决定了这个算法的时间复杂度，但是利用二分搜索更能提升算法效率，说不准就卡那么几毫秒。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * 查找列表中是否存在某元素，利用[binarySearch]二分查找
 * @author xmmmmmovo
 * @date 2020/7/28 11:49
 * @param list 列表
 * @param key 需要查找的元素
 * @return 返回是否存在
 * @since version-1.0
 */
fun <T : Comparable<T>> containsInList(list: List<T>, key: T): Boolean {
    val sorted = list.sorted()
    // 这里调用了上面的函数
    val res = binarySearch(sorted, key)
    return res != -1
}

时间复杂度：
$$
\mathcal{O}(Nlog_2N + log_2N)\\
=\mathcal{O}(Nlog_2N)
$$
空间复杂度:
$$
\mathcal{O}(N)
$$
因为启用了额外的数组。

三数之和

本题目也可以使用二分搜索做，最开始是使用蛮力法解决，时间复杂度为$\mathcal{O}(N^3)$，将其中最后一个元素的选取改为二分查找后便成为了$\mathcal{O}(N^2)$，复杂度大大降低。原理就是先排序，依旧是两重循环找出前两个数字，第三个数值利用二分法从剩余元素中找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * 查找已排序元素中是否有重复元素
 * @author xmmmmmovo
 * @date 2020/7/28 11:50
 * @param list 列表
 * @return 是否存在重复元素
 * @since version-1.0
 */
fun <T : Comparable<T>> containsDuplicatesInSorted(list: List<T>): Boolean {
    for (i in 0 until list.size - 1) {
        if (list[i] == list[i + 1]) return true
    }
    return false
}

/**
 * 二分法[binarySearch]求三数之和
 * @author xmmmmmovo
 * @date 2020/7/28 16:09
 * @param list 数字列表
 * @return 满足和为0的所有组合的列表
 * @throws IllegalArgumentException 数组元素小于3个时抛出异常
 * @since version-1.0
 */
fun threeSumBinaryFast(list: List<Int>, num: Int): List<List<Int>> {
    val res = LinkedList<List<Int>>()
    val sl = list.sorted().run {
        if (containsDuplicatesInSorted(this))
            distinct()
        else
            this
    }
    if (list.size < 3) throw IllegalArgumentException("数组非重复元素小于3个!")
    for (i in sl.indices) {
        for (j in i + 1 until sl.size) {
            val k = binarySearch(sl, num - (sl[i] + sl[j]), j + 1)
            if (k != -1) {
                res.add(listOf(sl[i], sl[j], sl[k]))
            }
        }
    }

    return res
}

时间复杂度方面，排序+循环时间复杂度$\mathcal{O}(N\log_2N+N^2\log_2N)$，化简得：
$$
\mathcal{O}(N^2)
$$
空间复杂度:
$$
\mathcal{O}(N)
$$
排序产生的中间数组。

数组局部最小元素

题目是这样描述的：

题目描述
题目描述

思路已经很明确了，即是每一次都往小部分缩小1/2的范围，最终查找到的符合条件的mid就成功了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/**
 * 局部最小元素
 * @author xmmmmmovo
 * @date 2020/7/30 19:36
 * @param list 数字列表
 * @param _lo 左边界 默认为0
 * @param _hi 右边界 默认为list.size - 1
 * @return 最小元素数字
 * @throws IllegalArgumentException 数组元素小于3个时抛出异常
 * @since version-1.0
 */
fun partialMinElem(list: List<Number>, _lo: Int = 0, _hi: Int = list.size - 1): Int {
    if (list.size < 3) throw IllegalArgumentException("数组元素小于3个！")
    var lo = _lo
    var hi = _hi
    // 两边需要单独测试
    if (list[lo] < list[lo + 1]) return lo
    if (list[hi] < list[hi - 1]) return hi

    while (lo in _lo..hi && hi <= _hi) {
        // 取mid
        val mid = lo + (hi - lo) / 2
        /**
         * 这里分为三个情况
         * ↘↗直接返回
         * ↗↗往左走
         * ↗↘都可以，原题是往小的地方走(因为部分排序过的数组会更快)
         * ↘↘往右走
         * 总之就是往小的地方走
         */
        when {
            mid == _lo ->
                if (list[mid] < list[mid + 1]) return mid
                else lo = mid + 1
            mid == _hi ->
                if (list[mid] < list[mid - 1]) return mid
                else hi = mid - 1
            list[mid - 1] > list[mid] && list[mid] < list[mid + 1] -> {
                return mid
            }
            list[mid - 1] < list[mid] && list[mid] < list[mid + 1] -> {
                hi = mid - 1
            }
            list[mid - 1] < list[mid] && list[mid] > list[mid + 1] -> {
                if (list[mid - 1] >= list[mid + 1]) lo = mid + 1
                else hi = mid - 1
            }
            else -> {
                lo = mid + 1
            }
        }
    }

    // 当所有元素都是一样的时候才没有最小值，返回-1
    return -1
}

时间复杂度(最差)：
$$
\mathcal{O}(2log_2N)
$$
为什么是这个时间复杂度呢，因为在最差情况下，向一边走完之后发现没有结果，然后就往另一边走，才发现结果，所以总体是$\mathcal{O}(2log_2N)$。

空间复杂度：
$$
\mathcal{O}(1)
$$

矩阵局部最小元素

题目是这样描述的：

题目描述
题目描述

这个题目也是跟上个题目类似，就是每一次缩减1/2的大小，不过这个并非数组，而是一个矩阵，所以我们对于复杂度不能用上一个题目那种分析方式来写。本题目的思路便是先从最中间元素开始搜查，根据上一题目的四种情况进行讨论，横向讨论完在下一次用纵向讨论，这样每一次都是缩减1/2，最终找到负荷情况的i，j就可以了。

但其实这个题目混沌的一批，如果用遍历+二分的做法的话，就会使得时间复杂度成为$\mathcal{O}(Nlog_2N)$，而非题目所要求的$\mathcal{O}(N)$，所以才要一直二分下去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * 矩阵局部最小元素
 * @author xmmmmmovo
 * @date 2020/7/30 19:36
 * @param matrix 矩阵
 * @return 最小元素数字
 * @throws IllegalArgumentException 矩阵为空的时候抛出异常
 * @since version-1.0
 */
fun <T : Number> matrixPartialMinElem(matrix: List<List<T>>): Pair<Int, Int> {
    if (matrix.isEmpty()) throw IllegalArgumentException("矩阵不能为空！")
    var lor = 0
    var hir = matrix.size - 1

    while (lor <= hir) {
        val mr = lor + (hir - lor) / 2
        val kc = partialMinElem(matrix[mr])

        when {
            kc == -1 -> {
                lor++
            }
            mr == 0 ->
                if (matrix[mr + 1][kc] > matrix[mr][kc])
                    return Pair(mr, kc)
                else
                    lor = mr + 1
            mr == matrix.size - 1 ->
                if (matrix[mr][kc] < matrix[mr - 1][kc])
                    return Pair(mr, kc)
                else
                    hir = mr - 1
            matrix[mr - 1][kc] > matrix[mr][kc] && matrix[mr][kc] < matrix[mr + 1][kc] ->
                return Pair(mr, kc)
            matrix[mr - 1][kc] < matrix[mr][kc] && matrix[mr][kc] < matrix[mr + 1][kc] ->
                hir = mr - 1
            matrix[mr - 1][kc] < matrix[mr][kc] && matrix[mr][kc] > matrix[mr + 1][kc] ->
                if (matrix[mr - 1][kc] >= matrix[mr + 1][kc]) lor = mr + 1 else hir = mr - 1
            else -> lor = mr + 1
        }
    }

    return Pair(-1, -1)
}

时间复杂度方面：

这个我怎么推都是$\mathcal{O}((log_2N)^2)$的复杂度（其实有推出一个$\mathcal{O}(2N)$来，但是总感觉不是特别靠谱），如果有大佬能推出来$\mathcal{O}(N)$的复杂度可以在下面留言，感谢！

空间复杂度方面：
$$
\mathcal{O}(1)
$$
没什么好说的。

双调查找

题目是这样描述的：

image-20200802133247034
image-20200802133247034

可以发现，这个像是局部最小值的变形，这里面必定有极大值，所以我们把问题分解成了三个子问题：

  1. 找到最大值
  2. 向左二分找值
  3. 向右二分找值

这样三个二分查找总共最差则是$\mathcal{O}(3log_2N)$，满足题意。为什么这里可以直接用二分法找最大值呢，因为这个数组很特殊，先增后减，可以说局部最大值就是最大值，所以可以利用二分查找直接找出。

局部最大函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * 局部最大元素
 * @author xmmmmmovo
 * @date 2020/7/30 19:36
 * @param list 数字列表
 * @param _lo 左边界 默认为0
 * @param _hi 右边界 默认为list.size - 1
 * @return 最大元素下标
 * @throws IllegalArgumentException 数组元素小于3个时抛出异常
 * @since version-1.0
 */
fun <T : Comparable<T>> partialMaxElem(
    list: List<T>, _lo: Int = 0, _hi: Int = list.size - 1
): Int {
    var lo = _lo
    var hi = _hi

    while (lo <= hi) {
        // 取mid
        val mid = lo + (hi - lo) / 2
        when {
            mid == _lo ->
                if (list[mid] > list[mid + 1]) return mid
                else lo = mid + 1
            mid == _hi ->
                if (list[mid] > list[mid - 1]) return mid
                else hi = mid - 1
            list[mid - 1] < list[mid] && list[mid] > list[mid + 1] -> {
                return mid
            }
            list[mid - 1] > list[mid] && list[mid] > list[mid + 1] -> {
                hi = mid - 1
            }
            list[mid - 1] > list[mid] && list[mid] < list[mid + 1] -> {
                if (list[mid - 1] <= list[mid + 1]) lo = mid + 1
                else hi = mid - 1
            }
            else -> {
                lo = mid + 1
            }
        }
    }

    // 当所有元素都是一样的时候才没有最小值，返回-1
    return -1
}

双栈查找函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * 双调查找
 * @author xmmmmmovo
 * @date 2020/7/31 15:42
 * @param list 数字列表
 * @param _lo 左边界 默认为0
 * @param _hi 右边界 默认为list.size - 1
 * @return 查找元素下标
 * @throws IllegalArgumentException 查不到最大元素时抛出常
 * @since version-1.0
 */
fun <T : Comparable<T>> doubleToneSearch(
    list: List<T>, key: T, _lo: Int = 0, _hi: Int = list.size - 1
): Int {
    val mi = partialMaxElem(list)
    if (mi == -1)
        throw IllegalArgumentException("请输入正确的双调列表！")
    if (list[mi] == key)
        return mi
    val l = binarySearch(list, key, _lo, mi - 1)
    val r = binarySearch(list.subList(mi + 1, _hi + 1).reversed(), key)

    return when {
        r == -1 -> l
        l == -1 -> _hi - r
        else -> l
    }
}

时间复杂度（最差）：
$$
\mathcal{O}((\frac{1}{2}+\frac{1}{2}+2)log_2N) =\\
\mathcal{O}(3log_2N)
$$

空间复杂度：
$$
\mathcal{O}(N)
$$
用了一半的反转数组。

仅用加减实现的二分查找

题目是这样描述的：

image-20200802233108582
image-20200802233108582

说的挺高深的，其实就是利用倒了斐波那契数列，个人感觉可能还能有数列满足指数级，暂时还没时间去想，有空可能会去想。

为什么能用斐波那契数列来求解呢？这还要跟斐波那契数列的特性有关系，我们知道斐波那契数列的规律是这样的：
$$
\mathcal{f}(n)=
\begin{cases}
1, & \mbox{if }n\mbox{ is 1} \\
1, & \mbox{if }n\mbox{ is 2} \\
\mathcal{f}(n - 1) + \mathcal{f}(n-2), &\mbox{if }n\mbox{ is >=3}
\end{cases}
$$
所以从分割点的左右两边来看，都包含有f(1)..f(n-2)的所有信息，只不过右边比左边多出了f(n-1)，所以无论是左边分还是右边往下分，都是可以分离直到f(1)产生的，这就是为什么能用斐波那契数列代替二分搜索的原因。

知道了原因，我们就来思考条件，首先一个首要条件便是：列表大小必须是斐波那契数列其中的某个元素 - 1才可以进行，所以我们需要先将数组扩充到大于这个数组长度的最小斐波那契数列的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/**
 * 创建最大值大于[length]的第一个数
 * @author xmmmmmovo
 * @date 2020/8/3 1:01
 * @param length 最长值
 * @return 数列
 * @since version-1.0
 */
fun makeFibonacciListUntilLength(length: Int): List<Int> {
    return when (length) {
        0 -> emptyList()
        1 -> listOf(1, 1, 2)
        2 -> listOf(1, 1, 2, 3, 5)
        else -> {
            val fl = mutableListOf(1, 1)
            var nv = 2
            while (length > nv - 1) {
                fl.add(nv)
                nv += fl[fl.size - 2]
            }
            fl.add(nv)
            fl
        }
    }
}

/**
 * 斐波那契二分搜索
 * @author xmmmmmovo
 * @date 2020/7/31 16:09
 * @param list 列表
 * @param key 需要查找的值
 * @param _lo 左范围 默认为0
 * @param _hi 右范围 默认为list.size - 1
 * @return 查找到了就返回下标，没查找到就返回-1
 * @since version-1.0
 */
fun <T : Comparable<T>> fibonacciBinarySearch(
    list: List<T>, key: T, _lo: Int = 0, _hi: Int = list.size - 1
): Int {
    if (list.isEmpty()) return -1
    if (list.size < 3) return list.indexOf(key)

    // 此时最末尾的值肯定是刚好大于长度的那个
    val fbl = makeFibonacciListUntilLength(_hi - _lo + 1)
    val tl = list.toMutableList()
    tl.addAll(List((fbl.last() - 1 - list.size)) { list.last() })

    var lo = _lo
    var hi = if (_hi == list.lastIndex) tl.lastIndex else _hi
    var k = fbl.lastIndex

    while (lo <= hi) {
        val mid = lo + fbl[k - 1] - 1
        when {
            tl[mid] > key -> {
                hi = mid - 1
                k--
            }
            // 小堆就-2，因为少了f(n-1)的信息
            tl[mid] < key -> {
                lo = mid + 1
                k -= 2
            }
            else -> return if (mid >= _hi) list.lastIndex else mid
        }
    }

    return -1
}

时间复杂度：
$$
\mathcal{O}(log_2N)
$$
空间复杂度：
$$
\mathcal{O}(N)
$$
越往后来说空间增加都近似于前一个数值的$\frac{1}{3}$，所以空间复杂度约为$\mathcal{O}(N)$

Github

Github