大型未排序列表上的二进制搜索或线性搜索？ [英] Binary search or Linear search on large unsorted lists?

问题描述

我了解二进制搜索比排序列表中的线性搜索和大型列表更有效，但是如果我们怎么办？有一个很大的列表，但是没有排序，我们使用线性搜索或二进制搜索？

解决方案

二进制搜索的概念只适用于已排序的输入。只研究它的工作原理：

I understand that the Binary search is more efficient than the Linear search in a sorted list and a large list, but what if we have a large list but not sorted, which one we use linear search or binary search?

解决方案

The concept of binary search can only work on sorted inputs. Just research how it works: Binary search at Wikipedia.

Based on your original question "binary search or linear search on unsorted lists?" the answer clearly is linear search because binary search can not be used.

However could it be possible that you at least have some knowledge of the input structure? If yes you could use that to create a better solution. If it is completely random then obviously linear search is the best. But you could easily parallelize the search like seen here: Fastest way to search for an element in unsorted array.

---

Let me give you a small overview for binary search. I select a random number between 1 and 100. You can now guess the number and I will tell you if my number is lower, equals or greater than your guess.

Binary search would now guess the half of the search interval, 50. I answer the guess is too high. The search interval is now from 1 to 49 and binary search now goes for 25. It repeats the search until the element is found.

---

If your input is unsorted then this will not work anymore because if I tell you that my element is lower than 50 then it does not necessarily mean that it is stored left to 50, it could also be to the right because the input is unsorted.

Here is an image illustrating the algorithm (found by a quick Google search):

这篇关于大型未排序列表上的二进制搜索或线性搜索？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！