Searching Algorithms

Udemy - 【한글자막】 JavaScript 알고리즘 & 자료구조 마스터클래스

How do we search?

Given an array, the simplest way to search for an value is to look at every element in the array and check if it's the value we want.

JavaScript has search!

There are many different search methods on arrays in JavaScript:

• indexOf
• includes
• find
• findIndex

Linear Search Pseudocode

• This function accepts an array and a value
• Loop through the array and check if the current array element is equal to the value
• If it is, return the index at which the element is found
• If the value is never found, return -1

#Prac 24. Linear Search Exercise

Write a function called linearSearch which accepts an array and a value, and returns the index at which the value exists. If the value does not exist in the array, return -1.

Don't use indexOf to implement this function!

Examples:

1. linearSearch([10, 15, 20, 25, 30], 15) // 1
2. linearSearch([9, 8, 7, 6, 5, 4, 3, 2, 1, 0], 4) // 5
3. linearSearch([100], 100) // 0
4. linearSearch([1,2,3,4,5], 6) // -1
5. linearSearch([9, 8, 7, 6, 5, 4, 3, 2, 1, 0], 10) // -1
6. linearSearch([100], 200) // -1

---

function linearSearch(arr, num){
//  return arr.indexOf(num) //Don't use indexOf to implement this function!

    for(let i = 0; i < arr.length; i++){
        if(arr[i] === num) return i;
    }
    return -1;
}

선형 검색 시간복잡도:  O(n) , 데이터가 분류되지 않았을 때 사용할 수 있는 가장 좋은 방법.

---

Binary Search Pseudocode

• This function accepts a sorted array and a value
• Create a left pointer at the start of the array, and a right pointer at the end of the array
• While the left pointer comes before the right pointer:
  • Create a pointer in the middle
  • If you find the value you want, return the index
  • If the value is too small, move the left pointer up
  • If the value is too large, move the right pointer down

• If you never find the value, return -1

Examples:

1. binarySearch([1,2,3,4,5],2) // 1
2. binarySearch([1,2,3,4,5],3) // 2
3. binarySearch([1,2,3,4,5],5) // 4
4. binarySearch([1,2,3,4,5],6) // -1
5. binarySearch([5, 6, 10, 13, 14, 18, 30, 34, 35, 37,40, 44, 64, 79, 84, 86, 95, 96, 98, 99], 10) // 2
6. binarySearch([5, 6, 10, 13, 14, 18, 30, 34, 35, 37,40, 44, 64, 79, 84, 86, 95, 96, 98, 99], 95) // 16
7. binarySearch([5, 6, 10, 13, 14, 18, 30, 34, 35, 37,40, 44, 64, 79, 84, 86, 95, 96, 98, 99], 100) // -1
   

function binarySearch(arr, num){
    let start = 0;
    let end = arr.length -1;
    let middle = Math.floor((end + start)/2);
    // if(num === arr[start]) return start;
    // if(num === arr[end]) return end;
    // if(num > arr[end] || num < arr[start]) return -1;
    while(arr[middle] !== num && start <= end){
        if(num < arr[middle]){
          end = middle -1;
      } else {
          start = middle +1;
      }
        middle = Math.floor((end + start)/2);
    }
        return (arr[middle] === num) ? middle : -1;
}

이진 검색은 아주 빠릅니다.
물론 이진 검색은 분류된 배열에서만 제대로 작동한다는 점에 유의해야겠죠. 분류된 데이터가 없다면 아쉽지만 어쩔 수 없이 이진 검색에 미치지 못하는 선형 검색을 사용해야 하고요.

---

Naive String Search

• Suppose you want to count the number of times a smaller string appears in a longer string
• A straightforward approach involves checking pairs of characters individually

Pseudocode

• Loop over the longer string
• Loop over the shorter string
• If the characters don't match, break out of the inner loop
• If the characters do match, keep going
• If you complete the inner loop and find a match, increment the count of matches
• Return the count

function naiveSearch(long, short){
    var count = 0;
    for(var i = 0; i < long.length; i++){
        for(var j = 0; j < short.length; j++){
           if(short[j] !== long[i+j]) break;
           if(j === short.length - 1) count++;
        }
    }
    return count;
}

naiveSearch("lorie loled", "lol")

---

KMP String Search

• The Knutt-Morris-Pratt algorithm offers an improvement over the naive approach
• Published in 1977
• This algorithm more intelligently traverses the longer string to reduce the amount of redundant searching

Building the Table

function matchTable(word) {
  let arr = Array.from({ length: word.length }).fill(0);
  let suffixEnd = 1;
  let prefixEnd = 0;
  while (suffixEnd < word.length) {
    if (word[suffixEnd] === word[prefixEnd]) {
      // we can build a longer prefix based on this suffix
      // store the length of this longest prefix
      // move prefixEnd and suffixEnd
      prefixEnd += 1;
      arr[suffixEnd] = prefixEnd;
      suffixEnd += 1;
    } else if (word[suffixEnd] !== word[prefixEnd] && prefixEnd !== 0) {
      // there's a mismatch, so we can't build a larger prefix
      // move the prefixEnd to the position of the next largest prefix
      prefixEnd = arr[prefixEnd - 1];
    } else {
      // we can't build a proper prefix with any of the proper suffixes
      // let's move on
      arr[suffixEnd] = 0;
      suffixEnd += 1;
    }
  }
  return arr;
}

KMP - FTW!

function kmpSearch(long, short) {
  let table = matchTable(short);
  let shortIdx = 0;
  let longIdx = 0;
  let count = 0;
  while (longIdx < long.length - short.length + shortIdx + 1) {
    if (short[shortIdx] !== long[longIdx]) {
      // we found a mismatch :(
      // if we just started searching the short, move the long pointer
      // otherwise, move the short pointer to the end of the next potential prefix
      // that will lead to a match
      if (shortIdx === 0) longIdx += 1;
      else shortIdx = table[shortIdx - 1];
    } else {
      // we found a match! shift both pointers
      shortIdx += 1;
      longIdx += 1;
      // then check to see if we've found the substring in the large string
      if (shortIdx === short.length) {
        // we found a substring! increment the count
        // then move the short pointer to the end of the next potential prefix
        count++;
        shortIdx = table[shortIdx - 1];
      }
    }
  }
  return count;
}

Big O of Search Algorithms

Linear Search - O(n)

Binary Search - O(log n)

Naive String Search - O(nm)

KMP - O(n + m) time, O(m) space

Recap

• Searching is a very common task that we often take for granted
• When searching through an unsorted collection, linear search is the best we can do
• When searching through a sorted collection, we can find things very quickly with binary search
• KMP provides a linear time algorithm for searches in strings