Sort an array of strings with binary search and insert a new string

Question

Sort an array of strings with binary search and insert a new string

My current challenge involves working with an alphabetically sorted array of strings:

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

The task at hand is to insert the string "CQW" into the collection while maintaining the sorted order without having to re-sort the entire array.

My desired outcome is to have

["ABC", "BCD", "CAB", "CQW", "FGH", "JKL", "ZKL"];

after the insertion is completed in O(log n) time.

To achieve this, I am considering leveraging binary search to calculate the index at which the new element should be inserted.

I came across a binary search code snippet that can find the index of a string within the collection:

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

However, I am facing a challenge in modifying the code to return the exact index for inserting the string. How can this code be adjusted to achieve that? Is binary search the most efficient approach for this task?

javascript algorithm sorting

Answer 1

Answer №1

When inserting into an array, the worst-case scenario is always O(n) due to moving values around after insertion, along with an additional n or log n for finding the insertion point. One approach could be to append the value at one end of the array and then utilize insertion sort, as it performs well on nearly-sorted input data.

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

Alternatively, for scenarios where large arrays require O(n) complexity for insertion, a sorted doubly-linked list may be a better choice.

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 useful if you decide 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;
}

Answer 2

When inserting into an array, the worst-case scenario is always O(n) due to moving values around after insertion, along with an additional n or log n for finding the insertion point. One approach could be to append the value at one end of the array and then utilize insertion sort, as it performs well on nearly-sorted input data.

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

Alternatively, for scenarios where large arrays require O(n) complexity for insertion, a sorted doubly-linked list may be a better choice.

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 useful if you decide 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;
}

Answer 3

Answer №2

The middle value indicates the appropriate position. Update the return value of the function to also indicate if the item is already present in the collection.

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)

Output

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

Answer 4

The middle value indicates the appropriate position. Update the return value of the function to also indicate if the item is already present in the collection.

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)

Output

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

Answer 5

Answer №3

Regrettably, the previous answers provided are not entirely accurate. Due to my limited reputation, I am consolidating all my thoughts and suggestions into this answer.

In summary, the most practical solution is also the simplest:

collection.push(newString);
collection.sort();

If avoiding duplicates is necessary, here is an alternative approach:

if (!collection.includes(newString)) {
    collection.push(newString);
    collection.sort();
}

For scenarios where thousands of new strings need to be inserted in a loop, appending them to the original array first and then sorting at the end is recommended.

Assessment of other (less effective) solutions

After benchmarking various solutions, including my own, it became evident that simplicity prevails in actual usage. The push(), sort() method outperformed the alternatives.

Here's a breakdown of the testing process:

Create a sorted array of 10,000 random 3-character all-caps strings
Execute each proposed solution 10,000 times, inserting 10,000 new random strings of the same type into the sorted array
Analyze the time taken to insert 10,000 additional strings

Ensuring fairness, all methods were configured to reject duplicates.

The insertionSort method by Olian04 ranked last in terms of efficiency. The doubly-linked list method, also by Olian04, offered marginal speed improvements at the expense of increased code complexity. Notably, the binarySearch approach, while significantly faster, did not yield correct results.

Ultimately, the push, sort method emerged as the most efficient solution in practical scenarios. My personal method, which involves a linear scan and Array.prototype.splice(), proved to be moderately faster than push, sort.

Although binary search demonstrated superior speed, practical implementation challenges prevent its widespread recommendation.

In my specific use case of managing sorted arrays for autocomplete suggestions in HTML datalists, the negligible difference in insertion speeds among the proposed solutions renders the decision to opt for simplicity and built-in functions a logical one. Real-world applications rarely necessitate rapid-fire insertion of thousands of elements.

For those seeking an O(log n) search/insertion time, exploring binary search trees is recommended for optimized performance.

Answer 6

Regrettably, the previous answers provided are not entirely accurate. Due to my limited reputation, I am consolidating all my thoughts and suggestions into this answer.

In summary, the most practical solution is also the simplest:

collection.push(newString);
collection.sort();

If avoiding duplicates is necessary, here is an alternative approach:

if (!collection.includes(newString)) {
    collection.push(newString);
    collection.sort();
}

For scenarios where thousands of new strings need to be inserted in a loop, appending them to the original array first and then sorting at the end is recommended.

Assessment of other (less effective) solutions

After benchmarking various solutions, including my own, it became evident that simplicity prevails in actual usage. The push(), sort() method outperformed the alternatives.

Here's a breakdown of the testing process:

Create a sorted array of 10,000 random 3-character all-caps strings
Execute each proposed solution 10,000 times, inserting 10,000 new random strings of the same type into the sorted array
Analyze the time taken to insert 10,000 additional strings

Ensuring fairness, all methods were configured to reject duplicates.

The insertionSort method by Olian04 ranked last in terms of efficiency. The doubly-linked list method, also by Olian04, offered marginal speed improvements at the expense of increased code complexity. Notably, the binarySearch approach, while significantly faster, did not yield correct results.

Ultimately, the push, sort method emerged as the most efficient solution in practical scenarios. My personal method, which involves a linear scan and Array.prototype.splice(), proved to be moderately faster than push, sort.

Although binary search demonstrated superior speed, practical implementation challenges prevent its widespread recommendation.

In my specific use case of managing sorted arrays for autocomplete suggestions in HTML datalists, the negligible difference in insertion speeds among the proposed solutions renders the decision to opt for simplicity and built-in functions a logical one. Real-world applications rarely necessitate rapid-fire insertion of thousands of elements.

For those seeking an O(log n) search/insertion time, exploring binary search trees is recommended for optimized performance.

Sort an array of strings with binary search and insert a new string

Answer №1

Answer №2

Answer №3

Similar questions

Determine if the object's value is present

What is the proper way to send a list of lists from Ajax to Flask?

What is the correct way to incorporate scrollIntoView() using jQuery?

Is it preferable to include in the global scope or the local scope?

Send an array from PHP to jQuery using AJAX, then send the array back from jQuery to PHP

Material UI in React: A lengthy typography body necessitates a line break

Incorporate innerHTML by appending instead of overwriting

Trouble arises when trying to load angular ui-bootstrap using require.js unless I change the name to ui.bootstrap

"Create a function that allows for the dynamic addition of elements to a

Executing a secondary API based on the data received from the initial API call

Struggling to make partial updates to a field within my CRUD update function

Is there a way to modify the color of my question post-submission?

Having difficulty retrieving the selected value in JSPDF

For the past two days, there has been an ongoing issue that I just can't seem to figure out when running npm start

Encountering a TypeError stating that the "option is undefined" error has occurred

The useRouter hook from next/router was unable to connect because NextRouter was not activated

React unable to properly render Array Map method

How can data be shared between two functional child components in a React application?

Tips for replacing the values obtained during parsing an XML document

Whenever a new entry is made into the textfield, the onChange feature triggers a reset on the content within the textfield