Javascript二进制搜索/插入性能 [英] Javascript Binary Search/Insertion Preformance

问题描述

function binarySearch(value)
{
    var startIndex = 0,
        stopIndex = words.length - 1,
        middle = Math.floor((stopIndex + startIndex) / 2);

    while (words[middle] != value && startIndex < stopIndex) {
        // adjust search area
        if (value < words[middle]) {
            stopIndex = middle - 1;
        } else if (value > words[middle]) {
            startIndex = middle + 1;
        }

        // recalculate middle
        middle = Math.floor((stopIndex + startIndex) / 2);
    }
}

我正在以数组格式列出大量单词:

I am making a large list of words in the format of an array:

例如["a","ab","abc","b"]

按字母顺序.我遇到的问题是修改二进制搜索算法，以将单词添加到正确的位置，然后更新?

In alphabetical order. The problem I'm having is modifying my binary search algorithm to add the word in the correct place and then update?

将单词添加到有序数组中的最佳性能方法是什么?为什么是最好的方法呢?

Whats the best way performance-wise to add a word into an ordered array? And why is it the best way to do it?

推荐答案

最好的方法是使用树，因为对于数组而言，这种操作可能具有线性算法复杂性.

The best way is to use trees instead, since for an array such an operation is likely to have linear algorithmic complexity.

如果您想坚持使用数组，建议您使用 splice splice 插入方法.

If you'd like to stick with the arrays, I suggest that you use the splice method for insertion.

这篇关于Javascript二进制搜索/插入性能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！