Find the Index of the First Occurrence in a String

To solve this coding challenge, the task is to find the first occurrence of a substring (needle) within another string (haystack). The solution provided uses a built-in JavaScript function indexOf, which directly solves the problem by returning the index of the first occurrence of the needle in the haystack. If the needle is not found, indexOf returns -1.

Let's break down the steps to solve this without relying on the built-in indexOf function, for a deeper understanding:

1. Check for Edge Cases:

First, we need to handle some edge cases. If the needle is an empty string, we can consider the index of the first occurrence to be 0, since an empty string technically occurs at every index. If the haystack is empty, or if the needle is longer than the haystack, the needle cannot be found, so we return -1.

2. Iterate Over the Haystack:

Loop through the haystack string, up to the point where the remaining characters are at least as many as the length of the needle. This is because if there are fewer characters left in the haystack than the length of the needle, the needle cannot possibly fit.

3. Match the Needle:

For each character in the haystack that could potentially be the start of an occurrence of the needle, check if the substring of the haystack starting from that character, of the same length as the needle, matches the needle.

4. Return the Index:

If a match is found, return the current index. This is the first occurrence of the needle in the haystack.

5. Return -1 if Not Found:

If the loop completes and no match is found, return -1.

Pseudo Code:

                                        
FUNCTION findFirstOccurrence(haystack, needle)
    IF needle IS EMPTY
        RETURN 0  // An empty needle is found at the beginning

    FOR each startingPosition IN haystack FROM 0 TO LENGTH(haystack) - LENGTH(needle)
        matchFound = TRUE

        FOR each characterPosition IN needle FROM 0 TO LENGTH(needle) - 1
            IF haystack[startingPosition + characterPosition] != needle[characterPosition]
                matchFound = FALSE
                BREAK  // Exit the inner loop as soon as a mismatch is found

        IF matchFound
            RETURN startingPosition  // Return the index of the first match

    RETURN -1  // Return -1 if no match is found
END FUNCTION
                                    

This pseudo code provides a step-by-step approach to find the first occurrence of needle in haystack without using any built-in string search functions, demonstrating the underlying algorithmic logic.