Searching algorithme

• 문자열로 된 배열에서 문자열을 찾는 알고리즘
• indexOf로 접근 가능한 것이 있으면 index 반환, 없으면 -1 반환
• 이걸 어떻게 메서드 사용하지 않고 알고리즘으로 하는지?

 

목적

• describe what is a searching algorithm is
• implement linear search on arrays
• implement binary search on sorted arrays
• implement a naive string searching algorithm
• implement the KMP string searching algorithm
  • Knuth–Morris–Pratt algorithm

 

1. Linear search on arrays

• It is the simplest way
• Search for an value is to look at every element in the array and check if it's the value we want.

 

JS has search

• indexOf
• includes
• find
• findIndex

 

How search works? answer: Linear search

 

Exercise

• This function acceps 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

 

My try

function linearSearch(array, value) {
  for (let i = 0; i < array.length; i++) {
    if (i === value) {
      return true;
    } else return -1;
  }
}

잘못한 것

1. array에 해당하는 i를 value와 비교해야하는데, i를 비교하였음

2. 찾았을 시 반환값이 i인데, 반환값을 boolean으로 줘버렸음 (문제를 제대로 읽지 않음)

 

Solution

function linearSearch(array, value) {
  for (let i = 0; i < array.length; i++) {
    if (array[i] === value) {
      return i;
    }
  }
  return -1;
}

 

BigO: O(n)

Best: O(1), Average: O(n), Worst: O(n)

 

 

2. Binary search on sorted arrays

• Binary search is a much faster form of search
• Rather than eliminating one element at a time, you can eliminate half of the remaining elements at a time
• Binary search on works on sorted arrays!

 

Divide and Conquer

split up in two pieces, pivot point is in the middle, check left and right, then eliminate, repeat!

 

Exercise

• 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 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

 

My try

function binarySearch(array, value) {
  let left = 0;
  let right = array.length - 1;
  while (left < right) {
    let middle = Math.round((array.length - 1) / 2);
    if (array[middle] === value) return middle;
    else if (array[middle] > value) left++;
    else if (array[middle] < value) right--;
  }
  return -1;
}

잘못된 점

1. middle의 정의, 위치

- middle을 while문 안에 정의하였음. 밖에 정의하여야함

- middle을 (array.length-1)/2로 정의하였는데, 이러면 left가 상승될 때 실제 middle을 찾아주지 못함. 따라서 left의 이동을 고려한 아래와 같이 정의 필요

Math.floor((start+end)/2)

*Math.floor하던 Math.ceil을 하던, 일정하게만 적용해주면 상관 없음

 

2. while문의 조건, break point 만들어 주기

left<right만 해주었는데, 이건 break point의 조건이고(이도 left<=end로 바꿔야함),

조건문을 array[middle] === value 일때,  !== value일때 2가지를 큰 조건으로 걸어주어야함

value가 아닐 때에는 break point가 생길 수 있도록(없으면 infinite loop를 돌게됨) 둘을 포함하는 && 걸어줌

while(array[middle] !== value && start <=end){

}
if(array[middle]===value){

}

 

Solution

function binarySearch(array, value){
  let start = 0;
  let end = array.length-1;
  let middle = Math.floor((start + end)/2)
  console.log(start, middle, end);

  while(array[middle] !== value && start <= end){
    if(value < array[middle]){
      end = middle -1;
    } else{
      start = middle +1;
    }
    middle = Math.floor((start + end)/2);
  }
  
  if(array[middle]===value){
    return middle;
  }
  return -1;
}

 

 

Shortened: if 대신 삼항연산자 사용

function binarySearch(array, value){
  let start = 0;
  let end = array.length-1;
  let middle = Math.floor((start + end)/2)
  console.log(start, middle, end);

  while(array[middle] !== value && start <= end){
    if(value < array[middle])end = middle -1;
    else start = middle +1;
    middle = Math.floor((start + end)/2);
  }
  return array[middle] === value ? middle: -1;
}

 

Big O

Worst/average: O(log n) , Best: O(1)

 

 

3. Naive String search

Count the number of times a smaller string appears in a longer string

A straightforward approach involves checking pairs of characters individually

• Long string: wowomgzomg
• Short string: omg
• 2 matches

 

Pseudocode

• function that takes two string, longer string, shorter string
• loop over the longer string
• nested loop: 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

 

Try

function navieSearch(long, short) {
  let count = 0;
  for (let i = 0; i < long.length; i++) {
    for (let j = 0; j < short.length; j++) {
      if (i !== j) {
        return;
        //break out of the inner loop
      } else {
        return;
        //keep going
      }
    }
  }
  count++;
  return count;
  //increment the count of matches
}

잘못된 점 

1. 배열에서 index (i)와 i의 value에 대한 착각

i의 value와 비교해야하는데 i(index)자체를 비교함

*위에도 했던 실수

2. break문을 몰랐음

break 문은 현재 반복문, switch문, 또는 label문을 종료하고, 그 다음 문으로 프로그램 제어를 넘깁니다.

MDN | break

 

3. 비교방법

4. match가 될 때 어떻게 확인할지에 대한 고민이 없었음

if you complete the inner loop and find a match, increment the count of matches

이 부분에서 끝까지 같은게 맞는지 어떻게 확인하는지에 대한 고민이 없었음

 

 

Solution

function navieSearch(long, short) {
  let count = 0;
  for (let i = 0; i < long.length; i++) {
    for (let j = 0; j < short.length; j++) {
      //console.log(long[i],short[j],long[i+j])
      if (short[j] !== long[i + j]) {
        //console.log("BREAK!")
        break;
      }
      if (j === short.length - 1) {
        //마지막까지 갔을 때   
        //console.log("FOUND ONE")
        count++;
      }
    }
  }
  return count;
}

navieSearch("wowomgzomg", "omg");