chapter_divide_and_conquer/binary_search_recur/

[giscus[bot]]

chapter_divide_and_conquer/binary_search_recur/

动画图解、一键运行的数据结构与算法教程

https://www.hello-algo.com/chapter_divide_and_conquer/binary_search_recur/

[bubble9um]

脑袋好痒，感觉要长🧠了

[krahets]

哈哈哈哈哈

[Yuhao-Luo]

Hi, 请问这里dfs的二分查找，空间复杂度是不是O(n)（最差要调用n个递归栈）？

[krahets]

Hi，空间复杂度也是 $O(\log n)$ ，因为每轮都排除一半元素，因此最差递归深度就是 $\log n$ 。

[zqzwj]

二分查找是基于有序数组

[Doub1e007]

有算法的思路，但是让自己上手搓代码就不太行怎么破呜呜~

[krahets]

勤加练习～

[WalkerInAI]

• Python
  在 /binary_search_recur.py/ 中，如果 查询目标target 在 指定搜索区间nums 的外面，函数 dfs 会一直运行下去
  请问我的理解是否正确？

[krahets]

不会，函数 dfs 能够正确处理这种情况。
（遇到这类问题，最好的方式是自己运行测试一下）

[travonf]

我不喜欢写else，如果每一个if条件后面都是return，可以不用写else了。

def bisect(a, x, i=None, j=None):
    if i is None:
        i = 0
    if j is None:
        j = len(a) - 1
    if i > j:
        return -1
    m = (i + j) // 2
    if a[m] == x:
        return m
    if a[m] > x:
        return bisect(a, x, i, m - 1)
    if a[m] < x:
        return bisect(a, x, m + 1, j)


if __name__ == '__main__':
    print(bisect(list(range(10, 20)), 10))  # 0
    print(bisect(list(range(10, 20)), 11))  # 1
    print(bisect(list(range(10, 20)), 13))  # 3
    print(bisect(list(range(10, 20)), 15))  # 5
    print(bisect(list(range(10, 20)), 17))  # 7
    print(bisect(list(range(10, 20)), 19))  # 9

[MambaFly]

输入一个无序序列，首先用排序算法得到有序序列，又和上一章联系起来了