Finding the insertion index

Let's say that you want to add a value to a list that's already sorted. Using push() will insert the value at the end of the list, and this isn't what you want. The insert() method can put the value at a particular index—you just have to figure out which index to use to keep the list sorted:

const sortedInsert = (item, list) => {
let low = 0;
let high = list.count();

while (low < high) {
const mid = (low + high) >>> 1;
if (item > list.get(mid)) {
low = mid + 1;
} else {
high = mid;
}
}
return list.insert(low, item);
};

The sortedIndex() function takes a value and a list into which to insert the value as arguments. It then does a simple binary search to find the correct index that will maintain the sort order of the collection. Let's see how this function works in practice:

const myList = List.of(1, 3, 5);
const withTwo = sortedInsert(2, myList);
const withFour = sortedInsert(4, withTwo);

console.log('myList', myList.toJS());
// -> myList [ 1, 3, 5 ]
console.log('withTwo', withTwo.toJS());
// -> withTwo [ 1, 2, 3, 5 ]
console.log('withFour', withFour.toJS());
// -> withFour [ 1, 2, 3, 4, 5 ]

The withTwo list has the value 2 inserted in the correct position, and withFour has 4 in the correct position. The main advantage of implementing this approach is that you can avoid having to re-sort the entire collection after pushing a new value. Finding the correct insertion index to maintain the sort order isn't without it's downsides, though.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
18.223.160.61