我们可以对未排序的数组使用二进制搜索吗? [英] Can we use binary search with an unsorted array?

问题描述

我有一个看起来像

2 6 8 5 34 1 12

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

Can I use a binary search on some subarray?

推荐答案

您只能在一种未排序"数组上使用二进制搜索-

You can use binary search on only one kind of "unsorted" array - the rotated array.

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

It can be done in O(log n) time like a typical binary search, but uses an adjusted divide and conquer approach. You can find a discussion about it here.

这篇关于我们可以对未排序的数组使用二进制搜索吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！