JavaScript 專題（九）陣列中查詢指定元素

上一篇文章中，我們瞭解了陣列扁平化的思想，並學習了 lodash 是如何處理陣列扁平化的。
這次我們來討論在陣列中查詢元素時所用的一些方法，並且參考lodash來實現我們自己的工具方法

一、findIndex 和 findLastIndex

1.1 findIndex

findIndex()方法返回陣列中滿足提供的測試函數的第一個元素的索引。若沒有找到對應元素則返回-1。

const array1 = [5, 12, 8, 130, 44];

const isLargeNumber = (element) => element > 13;

console.log(array1.findIndex(isLargeNumber));
// expected output: 3

實現

Array.prototype.newFindIndex = function(callback) {
  const _arr = this;
  const len = _arr.length;
  for (let i = 0; i < len; i++) {
    if (callback(_arr[i], i, _arr)) {
      return i;
    }
  }
  return -1;
};

const array1 = [5, 12, 8, 130, 44];
const isLargeNumber = (element) => element > 13;
console.log(array1.newFindIndex(isLargeNumber));
// 3

1.2 findLastIndex

同樣當我們倒敘查詢首個滿足條件的方法時，可以這樣寫：

Array.prototype.newFindlastIndex = function(callback) {
  const _arr = this;
  const len = _arr.length;
  for (let i = len - 1; i >= 0; i--) {
    if (callback(_arr[i], i, _arr)) {
      return i;
    }
  }
  return -1;
};

const array1 = [5, 12, 8, 130, 44];
const isLargeNumber = (element) => element > 13;
console.log(array1.newFindlastIndex(isLargeNumber));
// 4

上面的程式碼，和正序查詢很相似，僅僅改變遍歷的條件。

1.3 合併 findIndex 和 findLastIndex

大家可以看到，除了迴圈的條件不同，兩個方法幾乎一模一樣，參考 lodash，我們將兩個方法精簡一下

/**
 * @private
 * @param {Array} array The array to inspect.
 * @param {Function} predicate The function invoked per iteration.
 * @param {boolean} [fromRight] 從右向左查詢
 * @returns {number} 返回第一個符合條件元素的下標或-1
 */
function baseFindIndex(array, predicate, fromRight) {
  const { length } = array;
  let index = fromRight ? length : -1; // 確定下標的邊界

  while (fromRight ? index-- : ++index < length) {
    // index-- 用於倒序邊界
    // ++index 用於正序的邊界
    if (predicate(array[index], index, array)) {
      return index;
    }
  }
  return -1;
}

再來看看它的兄弟——underscore 的思路就是利用傳參的不同，返回不同的函數。

function createIndexFinder(dir) {
  return function(array, predicate, context) {
    const { length } = array;
    var index = dir > 0 ? 0 : length - 1;

    for (; index >= 0 && index < length; index += dir) {
      if (predicate.call(context, array[index], index, array)) return index;
    }
    return -1;
  };
}

var findIndex = createIndexFinder(1);
var findLastIndex = createIndexFinder(-1);

關於 findIndex 我們就告一段落了～，再來看看新的場景和實現吧！

二、sortIndex

在一個排好序的陣列中找到 value 對應的位置，即保證插入陣列後，依然保持有序的狀態。

const arr = [1, 3, 5];
sortedIndex(arr, 0); // 0
// 不需要插入arr

那麼這個又該如何實現呢？

2.1 遍歷

遍歷大家都能想到，雖然它不一定最優解：

function sortIndex(array, value) {
  for (let i = 0; i < array.length; i++) {
    if (array[i] > value) {
      return i;
    }
  }
  return array.length;
}

2.2 二分法

function sortIndex(array, value) {
  let low = 0,
    high = array.length;
  while (low < high) {
    let mid = Math.floor((low + high) / 2);
    if (array[mid] < value) {
      low = mid + 1;
    } else {
      high = mid;
    }
  }
  return high;
}

三、indexOf 和 lastIndexOf

• indexOf()：返回在陣列中可以找到一個給定元素的第一個索引，如果不存在則返回-1。從陣列的前面向後查詢，從 fromIndex 處開始。
• lastIndexOf() ：返回指定元素在陣列中的最後一個的索引，如果不存在則返回-1。從陣列的後面向前查詢，從 fromIndex 處開始。

3.1 indexOf 的第一版實現

function indexOf(array, value) {
  for (let i = 0; i < array.length; i++) {
    if (array[i] === value) {
      return i;
    }
  }
  return -1;
}

emmmm…在看過 findIndex 和 lastFindIndex 的實現後，indexOf 也要整整齊齊的啊～

3.2 indexOf 和 lastIndexOf 通用第一版

通過引數來建立不同的查詢方法

function createIndexOf(dir) {
  return function(array, value) {
    let index = dir > 0 ? 0 : arr.length - 1;
    for (; index >= 0 && index < arr.length; index += dir) {
      if (array[i] === value) {
        return i;
      }
    }
    return -1;
  };
}

3.3 indexOf 和 lastIndexOf 通用第二版

這一次，我們允許指定查詢位置，我們來看看 fromIndex 的作用：

設定開始查詢的位置。如果該索引值大於或等於陣列長度，意味著不會在陣列裡查詢，返回 -1。
如果引數中提供的索引值是一個負值，則將其作為陣列末尾的一個抵消，即 -1 表示從最後一個元素開始查詢，-2 表示從倒數第二個元素開始查詢 ，以此類推。
注意：如果引數中提供的索引值是一個負值，仍然從前向後查詢陣列。如果抵消後的索引值仍小於 0，則整個陣列都將會被查詢。其預設值為 0。

function createIndexOf(dir) {
  return function(array, value, fromIndex) {
    // 設定開始查詢的位置。如果該索引值大於或等於陣列長度，意味著不會在陣列裡查詢，返回 -1。
    let length = array == null ? 0 : array.length;
    let i = 0;
    if (!length) return -1;
    if (fromIndex >= length) return -1;
    if (typeof fromIndex === "number") {
      if (dir > 0) {
        // 正序
        // 起始點>=0，沿用起始點，否則起始點為從後向前數fromIndex
        i = fromIndex >= 0 ? fromIndex : Math.max(length + fromIndex, 0);
      } else {
        // 倒序
        // 起始點>=0，沿用起始點，否則起始點為從後向前數fromIndex
        length =
          fromIndex >= 0
            ? Math.min(fromIndex + 1, length)
            : fromIndex + length + 1;
      }
    }
    // 起始下標
    for (
      fromIndex = dir > 0 ? i : length - 1;
      fromIndex >= 0 && fromIndex < length;
      fromIndex += dir
    ) {
      if (array[fromIndex] === item) return fromIndex;
    }
    return -1;
  };
}

寫到這裡我們在陣列中查詢元素就結束了，自己實現的和loadsh或underscore還是有很大區別的，如果大家對上面三節的程式碼任意有更好的實現，請一定寫在留言區哦～

參考

• 學underscore在陣列中查詢指定元素
• lodash

寫在最後

JavaScript 系列：

1. 《JavaScript 內功進階系列》（已完結）
2. 《JavaScript 專項系列》（持續更新）

關於我

• 花名：餘光（沉迷 JS，虛心學習中）
• WX：j565017805

其他沉澱

• Js版LeetCode題解
• 前端進階筆記
• 我的 CSDN 部落格
• 我的 GitHub

這是文章所在 GitHub 倉庫的傳送門，如果真的對您有所幫助，希望可以點個 star，這是對我最大的鼓勵 ～