Як знайти індекс, де число належить до масиву в JavaScript

Сортування - дуже важливе поняття при написанні алгоритмів. Існують всі види сортів: сортування за бульбашками, сортування за оболонкою, сортування за блоками, сортування за гребінцем, сортування коктейлів, сортування за гномами - я їх не вигадую!

Цей виклик дає нам змогу зазирнути у дивовижний світ. Ми маємо відсортувати масив чисел від найменшого до найбільшого і з’ясувати, де дане число належить до цього масиву.

Інструкції з алгоритму

Повертає найнижчий індекс, при якому значення (другий аргумент) слід вставити в масив (перший аргумент) після його сортування. Повернене значення має бути числом. Наприклад, getIndexToIns([1,2,3,4], 1.5)повинно повертатися, 1оскільки воно більше 1(індекс 0), але менше 2(індекс 1). Так само, getIndexToIns([20,3,5], 19)повинно повертатися, 2оскільки як тільки масив буде відсортовано, він буде виглядати [3,5,20]і 19буде менше 20(індекс 2) і більше 5(індекс 1).
function getIndexToIns(arr, num) { return num; } getIndexToIns([40, 60], 50);

Надані тестові кейси

  • getIndexToIns([10, 20, 30, 40, 50], 35)повинен повернутися 3.
  • getIndexToIns([10, 20, 30, 40, 50], 35) повинен повернути номер.
  • getIndexToIns([10, 20, 30, 40, 50], 30)повинен повернутися 2.
  • getIndexToIns([10, 20, 30, 40, 50], 30) повинен повернути номер.
  • getIndexToIns([40, 60], 50)повинен повернутися 1.
  • getIndexToIns([40, 60], 50) повинен повернути номер.
  • getIndexToIns([3, 10, 5], 3)повинен повернутися 0.
  • getIndexToIns([3, 10, 5], 3) повинен повернути номер.
  • getIndexToIns([5, 3, 20, 3], 5)повинен повернутися 2.
  • getIndexToIns([5, 3, 20, 3], 5) повинен повернути номер.
  • getIndexToIns([2, 20, 10], 19)повинен повернутися 2.
  • getIndexToIns([2, 20, 10], 19) повинен повернути номер.
  • getIndexToIns([2, 5, 10], 15)повинен повернутися 3.
  • getIndexToIns([2, 5, 10], 15) повинен повернути номер.
  • getIndexToIns([], 1)повинен повернутися 0.
  • getIndexToIns([], 1) повинен повернути номер.

Рішення No1: .sort (), .indexOf ()

ПЕДАК

Розуміння проблеми : У нас є два входи, масив і число. Наша мета - повернути індекс нашого введеного числа після того, як він буде відсортований у вхідний масив.

Приклади / тестові випадки : Хороші люди у freeCodeCamp не повідомляють нам, яким чином слід сортувати вхідний масив, але надані тестові кейси дають зрозуміти, що вхідний масив слід сортувати від найменшого до найбільшого.

Зверніть увагу, що у двох останніх тестових випадках, де вхідний масив є порожнім масивом, є регістр краю.

Структура даних : Оскільки ми в кінцевому підсумку повертаємо індекс, дотримання масивів буде працювати для нас.

Ми будемо використовувати чудовий метод з назвою .indexOf():

.indexOf()повертає перший індекс, при якому елемент присутній у масиві, або a, -1якщо елемент відсутній взагалі. Наприклад:

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

Ми також будемо використовувати .concat()тут замість .push(). Чому? Оскільки, коли ви додаєте елемент до масиву за допомогою .push(), він повертає довжину нового масиву. Коли ви додаєте елемент до масиву за допомогою .concat(), він повертає сам новий масив. Наприклад:

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

Алгоритм :

  1. Вставити numв arr.
  2. Сортувати arrвід найменшого до найбільшого.
  3. Повернути індекс num.

Код : Дивіться нижче!

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

Без локальних змінних та коментарів:

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

Рішення No2: .sort (), .findIndex ()

ПЕДАК

Розуміння проблеми : У нас є два входи, масив і число. Наша мета - повернути індекс нашого введеного числа після того, як він буде відсортований у вхідний масив.

Приклади / тестові випадки : Хороші люди у freeCodeCamp не повідомляють нам, яким чином слід сортувати вхідний масив, але надані тестові кейси дають зрозуміти, що вхідний масив слід сортувати від найменшого до найбільшого.

При цьому рішенні слід враховувати два крайні випадки:

  1. Якщо вхідний масив порожній, тоді нам потрібно повернутися, 0оскільки numце буде єдиним елементом у цьому масиві, отже, в індексі 0.
  2. Якщо numб належав у самому кінці arrсортується від найменшого до найбільшого, тоді нам потрібно повернути довжину arr.

Структура даних : Оскільки ми в кінцевому підсумку повертаємо індекс, дотримання масивів буде працювати для нас.

Давайте .findIndex()перевіримо, як це допоможе вирішити цю проблему:

.findIndex()повертає індекс першого елемента масиву, який задовольняє надану функцію тестування. В іншому випадку він повертає -1, вказуючи, що жоден елемент не пройшов тест. Наприклад:

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

Це корисно для нас, оскільки ми можемо використовувати .findIndex()для порівняння введених даних numіз кожним числом у введеному тексті arrта з’ясування того, де він міститься в порядку від найменшого до найбільшого.

Алгоритм :

  1. Якщо arrце порожній масив, поверніть 0.
  2. Якщо numналежить в кінці відсортованого масиву, поверніть довжину arr.
  3. В іншому випадку повернення індексу numбуде, якщо arrйого буде відсортовано від найменшого до найбільшого.

Код : Дивіться нижче!

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

Без локальних змінних та коментарів:

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

Якщо у вас є інші рішення та / або пропозиції, будь ласка, поділіться з ними у коментарях!

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!