python - 二分查找和二分排序的区别

Question

1. 二分查找和二分排序有什么区别？（或者没有二进制排序之类的东西。）

2. 我可以对未排序的列表执行二进制搜索吗？（我对此有点清楚，有人可以向我解释一下。）

3. 如果我对未排序的列表执行二进制排序，然后在该（现在）排序列表中对元素进行二进制搜索，整个过程的时间复杂度是多少？

标签： pythonalgorithmsortingsearchbinary-search

Answer 1

2. 我可以在未排序的列表上执行二进制搜索吗？（我对此有点清楚，有人可以向我解释一下）

你不能，

二分搜索的核心思想是通过值比较来减少搜索空间。

例如查看 [1,2,3,4,5,6,7] 并且要搜索的元素是 5。在二分搜索中，我们在这种情况下查看中间元素 4，因为目标元素大于4 我们知道数组是排序的，我们只能查看右半部分 [5,6,7]

也可以在函数为 MONOTONOUS 的情况下实现二进制搜索，例如 [T , T , T , T , F , F , F] 您可以应用二进制搜索来使用此模板查找数组中的第一个 False

start=0, end=size
while(start<end)
    if(condition)
       end=mid
    else
       start=mid+1 
return start

返回 start 会给你第一个错误的元素。