I'm currently working on implementing a method to insert an object into a sorted array using binary search to determine the correct index for the new object.
You can view the code on codesanbox
The array I have is sorted using the following comparison method:
interface Comparator<A> {
(first: A, second: A): number;
}
function compareFields<A>(key: keyof A): Comparator<A> {
return (a: A, b: A): number => {
const first = a[key];
const second = b[key];
if (first < second) {
return 1;
} else if (first > second) {
return -1;
} else {
return 0;
}
};
}
To find the index, I am using the binarySearch method
function binarySearch<A>(
source: A[],
target: A,
comparator: Comparator<A>,
): number {
let first = 0;
let last = source.length - 1;
while (first <= last) {
const middle = (first + last) >>> 1;
const compareResult = comparator(source[middle], target);
if (compareResult === 0) {
return middle;
} else if (compareResult > 0) {
last = middle - 1;
} else {
first = middle + 1;
}
}
return -1;
}
Finally, I try to find the correct index and use the Array.splice method to add the new object to the source array
function binaryInsert<A extends any>(
source: A[],
target: A,
comparator: Comparator<A>,
): A[] {
const index = binarySearch(source, target, comparator);
return source.splice(index, 0, target);
}
const source = [
{ foo: 0 },
{ foo: 2 },
{ foo: 4 },
{ foo: 6 },
{ foo: 8 },
];
const expect = [
{ foo: 0 },
{ foo: 2 },
{ foo: 4 },
{ foo: 6 },
{ foo: 7 },
{ foo: 8 },
];
const target = { foo: 7 };
const result = binaryInsert(source, target, compareFields('foo'));
console.log({ expect, result });
However, I am receiving an empty array as a result. Can anyone help me identify where I might be going wrong?