在包含重复值的已排序和未排序数组中搜索和插入操作的时间复杂度
1-）对于排序数组，我使用了二分搜索。 我们知道，如果我们使用二分搜索，排序数组中搜索操作的最坏情况复杂度为 O(lg N)，其中 N 是数组中的项目数。 使用二分搜索在包含重复值的数组中进行搜索操作的最坏情况复杂度是多少？ 会是相同的 O(lg N) 吗？如果我说错了请纠正！！
另外，使用二分搜索在排序数组中进行 INSERT 操作的最坏情况是什么？ 我的猜测是 O(N)...是吗？
2-）对于未排序的数组，我使用了线性搜索。 现在我们有一个未排序的数组，它也接受重复的元素/值。 SEARCH 和 INSERT 操作的最佳最坏情况复杂度是多少？ 我认为我们可以使用线性搜索，这将为我们提供 O(N) 最坏情况下的搜索时间 和删除操作。 对于未排序的数组，我们可以做得更好吗？如果我们接受数组中的重复项，复杂性会改变吗？
1-)For sorted array I have used Binary Search.
We know that the worst case complexity for SEARCH operation in sorted array is O(lg N), if we use Binary Search, where N are the number of items in an array.
What is the worst case complexity for the search operation in the array that includes duplicate values, using binary search??
Will it be the be the same O(lg N)?? Please correct me if I am wrong!!
Also what is the worst case for INSERT operation in sorted array using binary search??
My guess is O(N).... is that right??
2-) For unsorted array I have used Linear search.
Now we have an unsorted array that also accepts duplicate element/values.
What are the best worst case complexity for both SEARCH and INSERT operation.
I think that we can use linear search that will give us O(N) worst case time for both search
and delete operations.
Can we do better than this for unsorted array and does the complexity changes if we accepts duplicates in the array.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
是的。是
最好的情况是无趣的。 （想想为什么会这样。）最坏的情况是 O(N)，插入除外。插入未排序的数组是快速的一次操作。 （再次，如果你没有看到它，请考虑一下。）
一般来说，重复几乎没有什么区别，除了极其病态的分布之外。
Yes.
The best case is uninteresting. (Think about why that might be.) The worst case is O(N), except for inserts. Inserts into an unsorted array are fast, one operation. (Again, think about it if you don't see it.)
In general, duplicates make little difference, except for extremely pathological distributions.
一些帮助，但不是整个解决方案。
Some help on the way - but not the entire solution.
我们可以更好地从无序数组中删除！由于在这种情况下顺序并不重要，我们可以将要删除的元素与最后一个元素交换，这样可以避免数组中元素不必要的移动。因此在 O(1) 时间内删除。
We can do better at deleting from an unordered array! As order doesn't matter in this case we can swap the element to be deleted with the last element which can avoid the unnecessary shifting of the elements in the array. Thus deleting in O(1) time.