javascript - Binärsökning och infoga i sorterad matris av objekt

Jag försöker implementera ett inför-objekt i en sorterad array som använder binärsökning för att hitta rätt index att lägga ett nytt objekt på.

Du kan se koden på codesanbox

Jag har en lista sorterad med följande jämförelsemetod:

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

För att hitta index i använder jag denna binarySearch-metod

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

Och slutligen försöker jag hitta rätt index och använda Array.spice-metoden för att lägga till ett nytt objekt i källarrayen

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

Som ett resultat får jag en tom array. Kan någon säga var jag har fel?

Svar #1

Det finns tre fel i din kod:

Felaktig användning av Array.splice

Kolla Array.splice-dokumentationen

Returvärde

En array som innehåller de raderade elementen.

• Om endast ett element tas bort returneras en array med ett element.
• Om inga element tas bort returneras en tom array.

Felaktig implementering av binärsökning

• vad händer om du får först > sist? Du returnerar -1 (felaktigt)

Felaktig hantering av negativt index som returneras av binärsökning

• du anger ett negativt index till slice som start
• igen, skapa dokument (parametrar: start):

Om det är negativt kommer det att börja så många element från slutet av arrayen.

• du sätter in målobjektet en position före slutet
• men det råkar vara rätt position i ditt testfall. Testet är grönt :)