js indexof 实现原理

JavaScript indexOf 的实现原理

JavaScript 的 indexOf 方法用于在字符串或数组中查找指定元素的首次出现位置。其实现原理基于线性搜索（顺序遍历），以下是具体细节：

字符串的 indexOf

字符串的 indexOf 方法会从指定位置开始，逐个字符比较目标子串与源字符串的匹配情况。如果找到匹配的子串，返回起始索引；否则返回 -1。

算法步骤：

1. 检查输入参数是否合法（如 searchValue 是否为字符串）。
2. 从 fromIndex 指定的位置开始遍历字符串。
3. 对于每个起始位置，比较目标子串与源字符串的对应字符。
4. 如果所有字符匹配，返回当前起始索引。
5. 遍历结束后未找到匹配项，返回 -1。

示例代码模拟实现：

function customIndexOf(str, searchValue, fromIndex = 0) {
  if (searchValue === "") return fromIndex >= str.length ? str.length : Math.min(fromIndex, str.length);
  for (let i = fromIndex; i <= str.length - searchValue.length; i++) {
    let match = true;
    for (let j = 0; j < searchValue.length; j++) {
      if (str[i + j] !== searchValue[j]) {
        match = false;
        break;
      }
    }
    if (match) return i;
  }
  return -1;
}

数组的 indexOf

数组的 indexOf 方法通过严格相等（===）比较元素，返回第一个匹配项的索引。

算法步骤：

1. 从 fromIndex 开始遍历数组。
2. 对每个元素使用 === 比较目标值。
3. 找到匹配项时返回当前索引。
4. 遍历结束后未找到匹配项，返回 -1。

示例代码模拟实现：

function customArrayIndexOf(arr, searchElement, fromIndex = 0) {
  for (let i = fromIndex; i < arr.length; i++) {
    if (arr[i] === searchElement) return i;
  }
  return -1;
}

性能特点

• 时间复杂度：最坏情况下为 O(n)，需要遍历整个字符串或数组。
• 优化：现代 JavaScript 引擎（如 V8）会针对长字符串或数组使用更高效的算法（如 Boyer-Moore），但标准实现仍基于线性搜索。

注意事项

1. 字符串的 indexOf 区分大小写。
2. 数组的 indexOf 使用严格相等，不适用于深比较或特殊对象。
3. fromIndex 为负数时，会被视为 length + fromIndex。