string.indexOf() under the hood

Hello, developers!

Today, I tried to implement the indexOf() method from scratch. So far I've found the following:

<code class="language-javascript">function myIndexOf(string, target, start = 0) {
    let l = target.length;

    // 调整起始索引，如果它是负数
    if (start < 0) {
        start = string.length + start;
    }

    // 确保起始索引在字符串长度范围内
    if (start < 0) {
        start = 0;
    } else if (start >= string.length) {
        return -1; // 目标索引超出字符串范围
    }

    // 循环遍历字符串
    for (let i = start; i <= string.length - l; i++) {
        if (string.substring(i, i + l) === target) {
            return i; // 找到目标子串
        }
    }

    return -1; // 未找到目标子串
}</code>

Code explanation:

The

indexOf() method accepts three parameters:

1. string: The string to search for.
2. target: The substring to find.
3. start: The index at which the search will start (default 0).

My first attempt:

My initial idea was simple: loop through the string and when I find string[i] === target, return i. If no match is found at the end of the loop, -1 is returned. The code is as follows:

<code class="language-javascript">// 此方法仅适用于单个字符的目标</code>

However, this method only works when target is a single character, since we are comparing character by character.

My second attempt:

Then I realized that I need to compare substrings if target is longer than one character. I use the substr() method to compare substrings that are the same length as target. The loop is adjusted to stop when there are enough characters left in the string to compare:

<code class="language-javascript">// 此方法处理多字符目标，但未处理start参数</code>

My third attempt:

Next, I need to handle the start parameter, which can be negative. The built-in indexOf() method starts searching from start when string.length start is negative. For example, if the string length is 10 and start is -4, the search will start at index 6 (i.e. 10 - 4).

To fix this, I updated the code to handle negative start values:

<code class="language-javascript">function myIndexOf(string, target, start = 0) {
    let l = target.length;

    if (start < 0) {
        start = string.length + start;
    }

    // ... (其余代码与第二次尝试相同)
}</code>

Final version:

Out of curiosity I wanted to handle start values ​​that are larger than the string length, I decided to modify the function so that if the start exceeds the string length, it continues to "wrap around" the string. This way the function will continue searching from the appropriate index after wrapping. The final solution uses this formula to adjust the starting index:

<code class="language-javascript">start = (string.length + start) % string.length;</code>

How it works:

The
• modulo operatorstart % string.length ensures that start is in the range -string.length to string.length.
• Added string.length to ensure that any negative results become positive.
The final modulo operation of
• ensures that the value of start is wrapped around and falls within valid index bounds.

Next I want to use binary search instead of linear search, what do you think?

The above is the detailed content of string.indexOf() under the hood. For more information, please follow other related articles on the PHP Chinese website!