Linear Search

As simple of a note as this looks like, I just want to track down going over basic DSA. Again.

Linear Search - iterating over the array, returning true if we found the value, false if not.

O(N) = n

Worst case: the value was not found, so we iterated over the whole array for nothing.

export default function linear_search(
  haystack: number[],
  needle: number,
): boolean {
  for (let i = 0; i < haystack.length; i++) {
    if (haystack[i] === needle) {
      return true;
    }
  }
 
  return false;
}

---

To recap from previous lesson:

TIP

Array - fixed size, continigous memory chunks.

There is not push, pop etc. Only insertion, which is actually overriding, and deletion, which means at a certain index we override the value with null.

Technically in JavaScript we do not have arrays in this traditional sense. type of of an array returns object.

Source

Algorithms & Data Structures | Learn Algorithms with TypeScript for Interviews | Frontend Masters