Algorithm practice: Find a needle in a haystack

23 Sep 2019 - John

For this simple exercise, we are given two strings. Our job is to find out if the second string is contained within the first one and return the index at which it occurs:

const haystack = "This is my haystack!";
const needle = "is my";
findNeedle(haystack, needle);
// Result: 5

Step 0: Break it into chunks

As always, before we even begin to think in code, we must be able to articulate the problem in plain English, so let’s make a list of the steps:

Create skeleton function that takes two arguments, one will be the needle and the other one will be the haystack.
Save the length of both strings in a variable
Implement an input check to exit the function if our needle is an empty string.
Write a loop that checks every position of the haystack for the needle.
If the needle is found, return the index of where it happened.

Step 1: The skeleton function

The first thing we need to do is write a scaffolding for our function:

const myHaystack = "This is my haystack!";
const myNeedle = "is my";
findNeedle = (needle, haystack) => {
  // stuff will happen here
}
console.log(findNeedle(myNeedle, myHaystack));

Step 2: Save the strings length in a variable

We’re going to use the length of both strings to test our inputs and to check for the result:

const myHaystack = "This is my haystack!";
const myNeedle = "is my";
findNeedle = (needle, haystack) => {
  let needleLength = needle.length;
  let haystackLength = haystack.length;
}
console.log(findNeedle(myNeedle, myHaystack));

Step 3: Check our inputs

We only need to check that our needle is not empty, we’ll check for the haystack later:

const myHaystack = "This is my haystack!";
const myNeedle = "is my";
findNeedle = (needle, haystack) => {
  let needleLength = needle.length;
  let haystackLength = haystack.length;
if (needleLength === 0) return 0;
}
console.log(findNeedle(myNeedle, myHaystack));

Step 4 and 5: The actual loop

const myHaystack = "This is my haystack!";
const myNeedle = "is my";
findNeedle = (needle, haystack) => {
  let needleLength = needle.length;
  let haystackLength = haystack.length;
  if (needleLength === 0) return 0;
for(i = 0; i < haystackLength; i++) {
    if (haystack.substr(i, needleLength === needle) return i;
  }

  return 0;
}
console.log(findNeedle(myNeedle, myHaystack));