Come trovare l'indice a cui appartiene un numero in un array in JavaScript

L'ordinamento è un concetto molto importante quando si scrivono algoritmi. Ce ne sono di tutti i tipi: bubble sort, shell sort, block sort, pettine sort, cocktail sort, gnome sort - non li sto inventando!

Questa sfida ci offre uno sguardo nel meraviglioso mondo di sorta. Dobbiamo ordinare un array di numeri dal minimo al più grande e scoprire dove un dato numero dovrebbe appartenere a quell'array.

Istruzioni dell'algoritmo

Restituisce l'indice più basso in corrispondenza del quale un valore (secondo argomento) deve essere inserito in un array (primo argomento) dopo che è stato ordinato. Il valore restituito dovrebbe essere un numero.Ad esempio, getIndexToIns([1,2,3,4], 1.5)dovrebbe restituire 1perché è maggiore di 1(indice 0), ma minore di 2(indice 1). Allo stesso modo, getIndexToIns([20,3,5], 19)dovrebbe restituire 2perché una volta che l'array è stato ordinato apparirà [3,5,20]ed 19è minore di 20(indice 2) e maggiore di 5(indice 1).
function getIndexToIns(arr, num) { return num; } getIndexToIns([40, 60], 50);

Casi di test forniti

  • getIndexToIns([10, 20, 30, 40, 50], 35)dovrebbe tornare 3.
  • getIndexToIns([10, 20, 30, 40, 50], 35) dovrebbe restituire un numero.
  • getIndexToIns([10, 20, 30, 40, 50], 30)dovrebbe tornare 2.
  • getIndexToIns([10, 20, 30, 40, 50], 30) dovrebbe restituire un numero.
  • getIndexToIns([40, 60], 50)dovrebbe tornare 1.
  • getIndexToIns([40, 60], 50) dovrebbe restituire un numero.
  • getIndexToIns([3, 10, 5], 3)dovrebbe tornare 0.
  • getIndexToIns([3, 10, 5], 3) dovrebbe restituire un numero.
  • getIndexToIns([5, 3, 20, 3], 5)dovrebbe tornare 2.
  • getIndexToIns([5, 3, 20, 3], 5) dovrebbe restituire un numero.
  • getIndexToIns([2, 20, 10], 19)dovrebbe tornare 2.
  • getIndexToIns([2, 20, 10], 19) dovrebbe restituire un numero.
  • getIndexToIns([2, 5, 10], 15)dovrebbe tornare 3.
  • getIndexToIns([2, 5, 10], 15) dovrebbe restituire un numero.
  • getIndexToIns([], 1)dovrebbe tornare 0.
  • getIndexToIns([], 1) dovrebbe restituire un numero.

Soluzione n. 1: .sort (), .indexOf ()

PEDAC

Comprensione del problema : abbiamo due input, un array e un numero. Il nostro obiettivo è restituire l'indice del nostro numero di input dopo che è stato ordinato nell'array di input.

Esempi / Casi di test : Le brave persone di freeCodeCamp non ci dicono in che modo dovrebbe essere ordinato l'array di input, ma i casi di test forniti chiariscono che l'array di input dovrebbe essere ordinato dal meno al più grande.

Si noti che c'è un caso limite negli ultimi due casi di test forniti in cui l'array di input è un array vuoto.

Struttura dei dati : poiché in ultima analisi stiamo restituendo un indice, restare fedeli agli array funzionerà per noi.

Utilizzeremo un metodo ingegnoso denominato .indexOf():

.indexOf()restituisce il primo indice in cui un elemento è presente in un array, o a -1se l'elemento non è affatto presente. Per esempio:

let food = ['pizza', 'ice cream', 'chips', 'hot dog', 'cake']
food.indexOf('chips')// returns 2food.indexOf('spaghetti')// returns -1

Useremo anche .concat()qui invece di .push(). Perché? Perché quando aggiungi un elemento a un array utilizzando .push(), restituisce la lunghezza del nuovo array. Quando aggiungi un elemento a un array utilizzando .concat(), restituisce il nuovo array stesso. Per esempio:

let array = [4, 10, 20, 37, 45]
array.push(98)// returns 6array.concat(98)// returns [4, 10, 20, 37, 45, 98]

Algoritmo :

  1. Inserisci numin arr.
  2. Ordina arrdal minimo al massimo.
  3. Restituisce l'indice di num.

Codice : vedi sotto!

function getIndexToIns(arr, num) { // Insert num into arr, creating a new array. let newArray = arr.concat(num) // [40, 60].concat(50) // [40, 60, 50] // Sort the new array from least to greatest. newArray.sort((a, b) => a - b) // [40, 60, 50].sort((a, b) => a - b) // [40, 50, 60] // Return the index of num which is now // in the correct place in the new array. return newArray.indexOf(num); // return [40, 50, 60].indexOf(50) // 1 } getIndexToIns([40, 60], 50);

Senza variabili locali e commenti:

function getIndexToIns(arr, num) { return arr.concat(num).sort((a, b) => a - b).indexOf(num); } getIndexToIns([40, 60], 50);

Soluzione 2: .sort (), .findIndex ()

PEDAC

Comprensione del problema : abbiamo due input, un array e un numero. Il nostro obiettivo è restituire l'indice del nostro numero di input dopo che è stato ordinato nell'array di input.

Esempi / Casi di test : Le brave persone di freeCodeCamp non ci dicono in che modo dovrebbe essere ordinato l'array di input, ma i casi di test forniti chiariscono che l'array di input dovrebbe essere ordinato dal meno al più grande.

Ci sono due casi limite da tenere in considerazione con questa soluzione:

  1. Se l'array di input è vuoto, allora dobbiamo tornare 0perché numsarebbe l' unico elemento in quell'array, quindi all'indice 0.
  2. Se numapparterrebbe alla fine di arrordinato dal minimo al più grande, è necessario restituire la lunghezza di arr.

Struttura dei dati : poiché in ultima analisi stiamo restituendo un indice, restare fedeli agli array funzionerà per noi.

Esaminiamo .findIndex()per vedere come aiuterà a risolvere questa sfida:

.findIndex()restituisce l'indice del primo elemento dell'array che soddisfa la funzione di test fornita. In caso contrario, restituisce -1, indicando che nessun elemento ha superato il test. Per esempio:

let numbers = [3, 17, 94, 15, 20] numbers.findIndex((currentNum) => currentNum % 2 == 0) // returns 2 numbers.findIndex((currentNum) => currentNum > 100) // returns -1

Questo è utile per noi perché possiamo usare .findIndex()per confrontare il nostro input numcon ogni numero nel nostro input arre capire dove si adatterebbe in ordine dal minimo al maggiore.

Algoritmo :

  1. Se arrè un array vuoto, restituisce 0.
  2. Se numappartiene alla fine dell'array ordinato, restituisce la lunghezza di arr.
  3. Altrimenti, restituirebbe l'indice numse arrfosse ordinato dal minimo al maggiore.

Codice : vedi sotto!

function getIndexToIns(arr, num) { // Sort arr from least to greatest. let sortedArray = arr.sort((a, b) => a - b) // [40, 60].sort((a, b) => a - b) // [40, 60] // Compare num to each number in sortedArray // and find the index where num is less than or equal to // a number in sortedArray. let index = sortedArray.findIndex((currentNum) => num  50  falsy // [40, 60].findIndex(60 => 50  truthy // returns 1 because num would fit like so [40, 50, 60] // Return the correct index of num. // If num belongs at the end of sortedArray or if arr is empty // return the length of arr. return index === -1 ? arr.length : index } getIndexToIns([40, 60], 50);

Senza variabili locali e commenti:

function getIndexToIns(arr, num) { let index = arr.sort((a, b) => a - b).findIndex((currentNum) => num <= currentNum) return index === -1 ? arr.length : index } getIndexToIns([40, 60], 50);

Se hai altre soluzioni e / o suggerimenti, condividi nei commenti!

This article is a part of the series freeCodeCamp Algorithm Scripting.

This article references freeCodeCamp Basic Algorithm Scripting: Where do I Belong.

You can follow me on Medium, LinkedIn, and GitHub!