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

Question

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

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

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

Answer 1

2. 我可以对未排序的列表进行二分查找吗？（我不太清楚，谁能给我解释一下）

不，你不能，

二分查找的核心思想是通过值比较来减少查找space

比如看[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 会给你第一个错误的元素。