二分搜索和一些用到二分思想的题目
前言 二分搜索可以说是应用非常广泛的一类算法了,非常多的暴力算法优化方案都是在一些条件下用二分,并且二分效率很高,可以让$\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 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 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 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 } 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 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) { 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 } } } 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 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
可以发现,这个像是局部最小值的变形,这里面必定有极大值 ,所以我们把问题分解成了三个子问题:
找到最大值 向左二分找值 向右二分找值 这样三个二分查找总共最差则是$\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 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) { 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 } } } 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 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
说的挺高深的,其实就是利用倒了斐波那契数列
,个人感觉可能还能有数列满足指数级,暂时还没时间去想,有空可能会去想。
为什么能用斐波那契数列
来求解呢?这还要跟斐波那契数列
的特性有关系,我们知道斐波那契数列
的规律是这样的: $$ \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 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 } } } 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-- } 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