假设我们需要查明电子邮件地址“demensdeum@gmail.com”是否包含在允许接收信件的电子邮件地址列表中.
让我们从第一个元素到最后一个元素遍历整个列表，检查该元素是否等于指定的地址–让我们实现一个线性搜索算法。但这需要很长时间，不是吗？
要回答这个问题，请使用“算法的时间复杂度”，“O”符号。最坏情况下线性搜索的操作时间等于数组元素的第n个数量，我们用“O”符号来写它–在）。接下来，我们需要解释一下，对于任何已知的算法，都存在三个性能指标——最好情况、最坏情况和平均情况的执行时间。例如，邮件地址“demensdeum@gmail.com”位于数组的第一个索引中，那么就会在第一步中找到它根据该算法，执行时间至多是“最佳”。 O(1)；如果在列表的末尾，那么这是最坏的情况– O(n)
但是软件实现的细节，硬件性能，它们应该影响大O吗？现在吸一口气，想象一下时间复杂度的计算是针对某种抽象的理想机计算的，其中只有这个算法，没有别的。
算法
好吧，事实证明线性搜索相当慢，让我们尝试使用二分搜索。首先，应该澄清的是，我们不会使用二进制数据；由于其工作的特殊性，因此给该方法起了这个名字。最初我们将数组排序为 字典顺序，然后算法取整个数组的范围，获取范围的中间元素，比较按字典顺序，并根据比较的结果，决定使用哪个范围来进一步搜索–当前的上半部分或下半部分。也就是说，在每个搜索步骤中，都会从两个可能的“结果”中做出决定。二元逻辑。重复此步骤，直到找到或未找到该单词（出现范围的下索引和上索引的交集）。
该算法的性能–最好的情况是立即在数组中间找到一个元素 O(1)，枚举的最坏情况是 O(log n)
陷阱
在实现二分查找时，我不仅遇到了编程语言库中字典比较缺乏标准化这个有趣的问题，甚至还发现缺乏统一的实现标准JavaScript 内的 localeCompare。 ECMAScript 标准允许该函数有不同的实现，这就是为什么当使用 localeCompare 进行排序时，可以在不同的 JavaScript 引擎上观察到完全不同的结果。
因此，为了使算法正确工作，有必要排序并仅使用相同的字典序比较算法，否则什么都不起作用。但是，例如，如果您尝试在 Scala 中对数组进行排序，并使用 Nodejs 进行搜索，而不实现您自己的排序/排序，那么除了对人性的失望之外，什么也没有等待您。
来源
<一href="https://ru.stackoverflow.com/questions/489888/%D0%A7%D1%82%D0%BE-%D1%82%D0%B0%D0%BA%D0%BE%D0%B5 -% D0%BB%D0%B5%D0%BA%D1%81%D0%B8%D0%BA%D0%BE%D0%B3%D1%80%D0%B0%D1%84%D0%B8%D1% 87%D0%B5%D1%81%D0%BA%D0%BE%D0 %B5-%D1%81%D1%80%D0%B0%D0%B2%D0%BD%D0%B5%D0%BD%D0%B8%D0%B5-%D0%B8-%D1%87% D1%82%D0%BE-%D0%BE%D0%BD%D0%BE- %D1%81%D0%BE%D0%B1%D0%BE%D0%B9-%D0%BF%D1%80%D0%B5%D0%B4%D1%81%D1%82%D0%B0% D0%B2%D0%BB%D1%8F%D0%B5%D1%82" target="_blank" rel="noopener">什么是词典比较，它代表什么？
Почему для вычисления сложности алгоритмов используется log N вместо lb N?
Двоичный поиск
Знай сложности алгоритмов
https://stackoverflow.com/questions/52941016/sorting-in-localecompare-in-javascript
源代码
https://gitlab.com/demensdeum/algorithms
