알고리즘 & 자료구조 7주차 [검색 알고리즘]

May 18, 2023 🐰

🤯 오늘 배울 개념은 Search!!!!

🔑 검색 알고리즘(Search)

• 검색의 다른 명칭이 탐색입니다.
  검색 엔진에는 엔진이라는 이름이 붙어 있는데,이를 엄밀하게 말하면 원하는 정보를 사람을 대신하여 찾아 주는 데이터 탐색 프로그램입니다.
  이 데이터 탐색 프로그램에서 사용하고 있는 알고리즘이 바로 탐색 알고리즘입니다.

objectives

• 검색 알고리즘이 뭔지 설명하기
• 배열에 선형 검색
• 이진 검색
• Naive 문자열 검색
• 검색 알고리즘에 대한 o(n)

🔑 선형 검색 (Linear Search)

데이터가 모인 집합(배열, 링크드리스트 등)의 처음부터 끝까지 하나씩 순서대로 비교하며 원하는 값을 찾아내는 알고리즘

Linear Search .. → 순차적으로 찾는 방식 (우리가 자주 사용했던 for,while문을 통한 맨 앞 또는 맨 뒤부터 순차적으로 찾는 방식)

• simple way - 모든 개별 항목을 순서대로 살펴보면서 우리가 원하는 값을 찾는다
• js 는 indexOf, includes, find .. 등의 함수를 가지고 있다.

👩🏻‍🌾 An Example Recursion

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:

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

👩🏻‍🌾basic solution

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

linearSearch([10, 15, 20, 25, 30], 15); // 1
linearSearch([9, 8, 7, 6, 5, 4, 3, 2, 1, 0], 4); // 5
let r = linearSearch([100], 100); // 0

console.log(r);

👩🏻‍🌾 Time Complexity Big O

O(n) 이지만 비효율적일수도 있다.

👍 Best!! → O(1)

🙂 avg..! → O(n)

😱 worst! → O(n)

🔑 이진 검색 (Binary Search)

이진 탐색은 정렬된 리스트에서 검색 범위를 줄여 나가면서 검색 값을 찾는 알고리즘
이진 탐색은 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 검색 범위가 절반으로 줄기 때문에 속도가 빠르다는 장점이 있음

👩🏻‍🌾 An Example Recursion

Write a function called binarySearch which accepts a 
sorted array and a value and returns the index at which 
the value exists. Otherwise, return -1.


Examples:

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

👩🏻‍🌾basic solution

 

 

function binarySearch(array, n) {
  // add whatever parameters you deem necessary - good luck!
  let left = 0;
  let right = array.length - 1;
  let middle = Math.floor((left + right) / 2);

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

  return -1;
}

let r = binarySearch([1, 2, 3, 4, 5], 2); // 1
binarySearch([1, 2, 3, 4, 5], 3); // 2
binarySearch([1, 2, 3, 4, 5], 5); // 4
binarySearch([1, 2, 3, 4, 5], 6); // -1

console.log(r);

👩🏻‍🌾 Time Complexity Big O

👍 Best!! → O(1)

🙂 avg..! → O(log n)

😱 worst! → O(log n)

🔑 Naive 문자열 검색(Naive String Search)

naive pattern searching은 패턴 검색 알고리즘 중에서 가장 간단한 알고리즘

단순히 문자를 처음부터 끝까지 하나하나 비교해가며 패턴을 찾기 때문에 작은 문자열에서 패턴을 찾을 때 유용

생각보다 이 방법으로 문제를 많이 풀었던 거 같다... 이름 없이 풀었던 solution이 이름이 있다니.....

"피실험체 89P13이 이름이였던 로켓이 라쿤로켓이였던 감동...!"

( 아직 가오겔3의 여운에 못빠져나옴...😭)

👩🏻‍🌾 An Example Recursion

문자열 내에 포함되는 것이 있는지 찾기!

👩🏻‍🌾basic solution

function naiveSearch(long, short) {
  let 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;
}

let r = naiveSearch("lorie loled", "lo");
console.log(r);

👩🏻‍🌾 Time Complexity Big O

🔑 Review

• linear, binary, naive.. 익숙한 방법들이였다. 사실 binary는 아직 익숙하진 않지만.. 이러한 방법들로 문제를 풀 때 문제에 맞게 풀어야한다는 생각이 든다.
• binary가 시간복잡도가 효율이 좋다고 그냥 사용하기에도 문제가 생길거 같다.
• 결국 취지는 다양한 알고리즘을 습득해 문제에 맞게 효율적으로 사용하는 스킬을 기르는거 같다.

💻 Source

• ✏️ Best JavaScript Data Structures & Algorithms Course by Udemy, last updated January 2022, accessed April 5, 2023 - https://www.udemy.com/
• ⌨️ reference gitHub - https://github.com/seunghyun0522/JavaScript-Algorizms-Data-Structure