我们可以对未排序的数组使用二进制搜索吗？

Question

我有一个看起来像的数组

2 6 8 5 34 1 12

我可以在某些子数组上使用二进制搜索吗？

Answer 1

您只能在一种“未排序”数组（旋转数组）上使用二进制搜索。

它可以O(log n)像典型的二进制搜索一样及时完成，但使用调整后的分而治之方法。您可以在此处找到有关它的讨论。

Answer 2

不，二分查找需要一个排序数组。您可能具有数组的其他属性，使您能够进行比单纯的迭代更有效的搜索，但二分搜索的本质要求对数据进行排序。

如果您知道数组的一部分已排序，您当然可以提取它，在那里执行二进制搜索并将其从其他线性搜索中排除。

Answer 3

你不能。“二分搜索”检查值是在左侧还是右侧，比较它何时小于或大于中心项。

数组：2 6 8 5 34 1 12

假设您想找到“1”，因此在第一次迭代中，该方法会将“1”与当前的中心元素（在本例中为“5”）进行比较。该方法会说：“由于 1 小于 5，我将在左侧搜索”，但是如果我们这样做，我们将永远找不到它，因为在左侧没有一个。

但是如果我们有： 1 2 5 6 8 12 34

请注意，1 小于 6（中心元素），因此在下一步中，算法将继续在左侧搜索，这没问题。因此，要使用“二进制搜索”，必须对元素进行排序。