Вставить строку в отсортированный массив строк с помощью двоичного поиска

Question

У меня есть следующий отсортированный по алфавиту массив строк:

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"));

Однако я изо всех сил пытался изменить его так, чтобы он возвращал точный индекс, по которому необходимо вставить строку. Как это можно изменить, чтобы оно работало? Является ли бинарный поиск наиболее эффективным способом сделать это?

Answer 1

Значение 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"]

Answer 2

Поскольку вы вставляете в массив, у вас всегда будет наихудший случай O(n) при простом перемещении значений вокруг «после» вставки (+ дополнительные n или log n для поиска места для введите значение в). Так что я бы либо просто добавил значение на одном конце массива, а затем отсортировал его с помощью сортировки вставкой (поскольку сортировка вставкой на самом деле является одним из более быстрых алгоритмов для почти отсортированных входных данных).

const insertionSort = (inputArr) => {
    const length = inputArr.length;
    for (let i = 1; i < length; i++) {
        const key = inputArr[i];
        let j = i - 1;
        while (j >= 0 && inputArr[j] > key) {
            inputArr[j + 1] = inputArr[j];
            j = j - 1;
        }
        inputArr[j + 1] = key;
    }
    return inputArr;
};

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

collection.push("CQW");
console.log(insertionSort(collection));

Или, если вы склонны иметь ОГРОМНЫЕ массивы и вам нужна O(n) сложность наихудшего случая для вставки; тогда я бы переместился в всегда отсортированный двусвязный список.

const linkedList = (value, next) => ({prev: null, value, next});
const insert = (node, value) => {
  if (node === null) {
    return false;
  }
  if (node.value < value) {
    return insert(node.next, value);
  }
  const newNode = linkedList(value, node);
  newNode.prev = node.prev;
  newNode.prev.next = newNode;
  node.prev = newNode;
  return true;
} 
const arrayToList = (arr) => arr.reverse().reduce((next, el) => {
  const list = linkedList(el, next);
  if (next) {
    next.prev = list;
  }
  return list;
}, null);
const printList = (list) => {
  const arr = [];
  let node = list;
  while (node) {
    arr.push(node.value);
    node = node.next;
  }
  console.log(arr);
};


const collection = ["ABC", "BCD", "CAB", "FGH", "JKL", "ZKL"];
const list = arrayToList(collection);
insert(list, "CQW");

printList(list);


// Some function that arent't used in the example
// but are very usefull if you decided to use this solution
const get = (list, index) => {
  let node = list;
  for (let i = 0; node; i++) {
    if (i === index) {
      return node.value;
    }
    node = node.next;
  }
  return null;
}
const set = (list, index, value) => {
  let node = list;
  for (let i = 0; node; i++) {
    if (i === index) {
      node.value = value;
      return true;
    }
    node = node.next;
  }
  return false;
}
const remove = (list, value) => {
  if (node === null) {
    return false;
  }
  if (node.value === value) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
    return true;
  }
  return remove(node.next, value);
}
const getIndex = (list, value) => {
  let node = list;
  for (let i = 0; node; i++) {
    if (node.value === value) {
      return i;
    }
    node = node.next;
  }
  return -1;
}