JavaScript算法题：查找数字在数组中的索引

系统管理员 2022-10-01 10:56 97阅读 0赞

> 翻译：疯狂的技术宅
> 
> 原文：[medium.freecodecamp.org/how-to-find…][medium.freecodecamp.org_how-to-find]

编写算法时，排序是一个非常重要的概念。它有各种各样的种类：冒泡排序、希尔排序、分块块排序，梳排序，鸡尾酒排序，侏儒排序 —— [这些可不是我瞎编的][Link 1]！

这个算法题能够让我们一睹精彩的世界。我们必须对数字数组进行升序排序，并找出给定数字在该数组中的位置。

### 算法说明 ###

> 将值（第二个参数）插入到数组（第一个参数）中，并返回其在排序后的数组中的最低索引。返回的值应该是一个数字。 例如 `getIndexToIns([1,2,3,4], 1.5)` 应该返回 `1`，因为 `1.5` 大于 `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);
    复制代码

[本算法题原题][Link 2]

### 测试用例 ###

*  `getIndexToIns([10, 20, 30, 40, 50], 35)` 应该返回一个数字 `3`。
 *  `getIndexToIns([10, 20, 30, 40, 50], 30)` 应该返回一个数字 `2`.
 *  `getIndexToIns([40, 60], 50)` 应该返回一个数字 `1`.
 *  `getIndexToIns([3, 10, 5], 3)` 应该返回一个数字 `0`.
 *  `getIndexToIns([5, 3, 20, 3], 5)` 应该返回一个数字 `2`.
 *  `getIndexToIns([2, 20, 10], 19)` 应该返回一个数字 `2`.
 *  `getIndexToIns([2, 5, 10], 15)` 应该返回一个数字 `3`.
 *  `getIndexToIns([], 1)` 应该返回一个数字 `0`.

### 解决方案＃1：`.sort()`，. indexOf`()` ###

#### PEDAC ####

**理解问题**：有两个输入：一个数组和一个数字。我们的目标是将输入的数字在输入数组后中排序后，再返回它的索引。 **示例/测试用例**：我们不知道输入的数组是以哪种方式排序的，但是提供的测试用例清楚地表明，输入的数组应该从小到大进行排序。

请注意，在最后一个测试用例中存在边界问题，其中输入数组是一个空数组。

**数据结构**：由于我们最终将会返回索引，因此应该坚持使用数组。

我们将会用一个名为 `.indexOf()` 的方法：

`.indexOf()` 返回元素在数组中出现的第一个索引，如果元素根本不存在则返回 `-1`。例如：

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

我们将使用 `.concat()` 而不是 `.push()`。为什么呢？因为当使用 `.push()` 向数组添加元素时，它会返回新数组的长度。而使用 `.concat()` 向数组添加元素时，它会返回新数组本身。例如：

let array = [4, 10, 20, 37, 45]
    array.push(98)
    // returns 6
    array.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);
    复制代码

### 解决方案＃2：`.sort()`，`.findIndex()` ###

#### PEDAC ####

这个解决方案需要考虑两个边界情况：

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`。

**代码**：

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 <= currentNum)
      // [40, 60].findIndex(40 => 50 <= 40) --> falsy
      // [40, 60].findIndex(60 => 50 <= 60) --> 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);
    复制代码

如果你有其他解决方案或建议，请在评论中分享！

## 欢迎关注前端公众号：前端先锋，获取前端工程化实用工具包。 ##

转载于:https://juejin.im/post/5cdd2a0c51882534b84ec574

[medium.freecodecamp.org_how-to-find]: https://link.juejin.im?target=https%3A%2F%2Fmedium.freecodecamp.org%2Fhow-to-find-the-index-where-a-number-belongs-in-an-array-in-javascript-9af8453a39a8
[Link 1]: https://link.juejin.im?target=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FSorting_algorithm
[Link 2]: https://link.juejin.im?target=https%3A%2F%2Flearn.freecodecamp.org%2Fjavascript-algorithms-and-data-structures%2Fbasic-algorithm-scripting%2Fwhere-do-i-belong%2F