Javascript 二进制搜索/插入预处理

Javascript Binary Search/Insertion Preformance

本文关键字：插入 预处理 搜索 二进制 Javascript      更新时间：2023-09-26
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);
    }
}

我正在以数组格式制作一个大型单词列表：

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

按字母顺序排列。我遇到的问题是修改我的二叉搜索算法以将单词添加到正确的位置，然后更新？

在

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

为了有效地插入二叉搜索，您需要让二叉搜索返回一些内容，指示如果找不到字符串，字符串在数组中的位置。

在其他语言中执行此操作的公认方法是返回字符串所属索引的按位补码。0 的按位补码是 -1,1 的按位补码是 -2,2 是 -3，依此类推。要在 JavaScript 中获取数字的按位补码，请使用 ~ 运算符。

示例代码：

/* 
    target: the object to search for in the array
    comparator: (optional) a method for comparing the target object type
    return value: index of a matching item in the array if one exists, otherwise the bitwise complement of the index where the item belongs
*/
Array.prototype.binarySearch = function (target, comparator) {
    var l = 0,
        h = this.length - 1,
        m, comparison;
    comparator = comparator || function (a, b) {
        return (a < b ? -1 : (a > b ? 1 : 0)); /* default comparison method if one was not provided */
    };
    while (l <= h) {
        m = (l + h) >>> 1; /* equivalent to Math.floor((l + h) / 2) but faster */
        comparison = comparator(this[m], target);
        if (comparison < 0) {
            l = m + 1;
        } else if (comparison > 0) {
            h = m - 1;
        } else {
            return m;
        }
    }
    return~l;
};

然后，您可以使用 binarySearch 方法编写自己的 binaryInsert 函数：

/*
    target: the object to insert into the array
    duplicate: (optional) whether to insert the object into the array even if a matching object already exists in the array (false by default)
    comparator: (optional) a method for comparing the target object type
    return value: the index where the object was inserted into the array, or the index of a matching object in the array if a match was found and the duplicate parameter was false 
*/
Array.prototype.binaryInsert = function (target, duplicate, comparator) {
    var i = this.binarySearch(target, comparator);
    if (i >= 0) { /* if the binarySearch return value was zero or positive, a matching object was found */
        if (!duplicate) {
            return i;
        }
    } else { /* if the return value was negative, the bitwise complement of the return value is the correct index for this object */
        i = ~i;
    }
    this.splice(i, 0, target);
    return i;
};

将这些方法原型化到数组对象上后，可以直接使用它们，如下所示：

var arr = [];
arr.binaryInsert("Zebra");
arr.binaryInsert("Aardvark");
arr.binaryInsert("Mongoose");
alert(arr);
/* [ "Aardvark", "Mongoose", "Zebra" ] */

随着项目数量的增加，这将比调用Array.sort()快得多

阵列属性键污染

请注意，如

上代码所示，将方法原型化到 Array 对象会导致方法显示为数组的可枚举属性，这可能会干扰在 for(var i in arr) 循环中枚举所有属性的任何逻辑。以 for(var i=0; i<arr.length; i++) 格式编写的循环仍将按设计工作。

如果您不需要支持 Internet Explorer 8 或更低版本，则可以避免直接调用Array.prototype，而是使用以下示例中的Object.defineProperty。

Object.defineProperty(Array.prototype, "binarySearch", {
value: function (target, comparator) {
    var l = 0,
        h = this.length - 1,
        m, comparison;
    comparator = comparator || function (a, b) {
        return (a < b ? -1 : (a > b ? 1 : 0));
    };
    while (l <= h) {
        m = (l + h) >>> 1;
        comparison = comparator(this[m], target);
        if (comparison < 0) {
            l = m + 1;
        } else if (comparison > 0) {
            h = m - 1;
        } else {
            return m;
        }
    }
    return~l;
}
});
Object.defineProperty(Array.prototype, "binaryInsert", {
value: function (target, duplicate, comparator) {
    var i = this.binarySearch(target, comparator);
    if (i >= 0) {
        if (!duplicate) {
            return i;
        }
    } else {
        i = ~i;
    }
    this.splice(i, 0, target);
    return i;
}
});

此方法将避免污染可枚举键，因此for(var i in arr)循环仍将按预期工作。

最好的方法是改用树，因为对于数组来说，这样的操作可能具有线性算法的复杂性。

如果你想坚持使用数组，我建议你使用拼接方法进行插入。

相关文章：