时间戳

首页 > 解决方案 > 使用二进制搜索将字符串插入排序的字符串数组

javascript - 使用二进制搜索将字符串插入排序的字符串数组

问题描述

我有以下按字母顺序排列的字符串数组：

let collection = ["ABC", "BCD", "CAB", "FGH", "JKL", "ZKL"];

我想"CQW"在集合中插入字符串，同时保留排序顺序，但不必重新对整个数组进行排序。

所以我想["ABC", "BCD", "CAB", "CQW", "FGH", "JKL", "ZKL"];在插入完成后O(log n)及时完成。

我认为使用二进制搜索计算我需要插入元素的索引是一个好主意。

我找到了以下用于二进制搜索的代码，如果它存在于集合中，它会检索字符串的索引：

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

  while (items[middle] != value && startIndex < stopIndex) {

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

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

  // Return -1 if element is not in collection
  return (items[middle] != value) ? -1 : middle;
}

let collection = ["ABC", "BCD", "CAB", "FGH", "JKL", "ZKL"];

console.log(binarySearch(collection, "CQW"));

但是，我一直在努力修改它，以便它返回需要插入字符串的精确索引。如何修改它以使其工作？二进制搜索是最有效的方法吗？

标签： javascriptalgorithmsorting

解决方案

该middle值应该告诉你把它放在哪里。修改函数的返回值，让它告诉你它是否已经在集合中

function binarySearch(items, value) {
  console.log('Searching for '+value)
  let startIndex = 0;
  let stopIndex = items.length - 1;
  let middle = Math.floor((stopIndex + startIndex) / 2);

  while (items[middle] != value && startIndex < stopIndex) {

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

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

  // Return -1 if element is not in collection
  // return (items[middle] != value) ? -1 : middle;
  return {
      found: items[middle] == value,
      middle: middle
  }
}

let collection = ["ABC", "BCD", "CAB", "FGH", "JKL", "ZKL"];
let item = "CQW"
result= binarySearch(collection, item);
console.log(result)
if(!result.found){
    console.log('Adding '+item+' at index '+result.middle)
    collection.splice(result.middle, 0, item);
}
console.log(collection)

输出

Searching for CQW
{found: false, middle: 3}
Adding CQW at index 3
["ABC", "BCD", "CAB", "CQW", "FGH", "JKL", "ZKL"]

推荐阅读