Algorithm - Search Algorithm

Search Algorithm

Linear Search

• 배열을 앞에서부터 순차적으로 탐색함
• linear search를 사용하는 built-in 메서드 : indexOf, includes, find, findIndex

Linear Search function

• 배열과 값을 인자로 받는 함수
• 값이 존재한다면 그 값의 index를 반환함
• 값이 존재하지 않는다면 -1을 반환함

// recursion
function linearSearch(arr, value){
  let index = 0;
  function helper(arr, value, index) {
      if (index >= arr.length) {
          return -1;
      }
      if (arr[index] === value) {
          return index;
      }
      return helper(arr, value, index + 1);
  }
  return helper(arr, value, index);
}

// for loop
function linearSearch(arr, value){
  for (let index = 0; index < arr.length; index++){
    if (arr[index] === value) return index;
  }
  return -1;
}

Linear Search - Big O notation

• linear search의 Big O notation
  • O(1) ~ O(N) => O(N)

Binary Search

• binary search는 훨씬 빠른 seach 형태임
• 한번에 남아있는 요소의 절반을 제거할 수 있음
• binary search는 정렬된 배열에서만 사용할 수 있음

Binary Search function

• 배열과 값을 인자로 받는 함수
• 배열의 첫 번째 요소를 left pointer에 배열의 마지막 요소를 right pointer에 할당함
• 배열의 중간에 있는 요소를 pointer에 할당함
  • pointer의 값이 value와 같다면 index를 반환함
  • pointer의 값이 value보다 작다면, left pointer를 올리고 그 사이의 중값값을 pointer에 할당함
  • pointer의 값이 value보다 크다면, right pointer를 내리고 그 사이의 중값값을 pointer에 할당함
• 값을 찾지 못한다면, -1을 반환함

// recursion
function binarySearch(arr, value){
  let leftIndex = 0;
  let rightIndex = arr.length - 1;
  function helper(leftIndex, rightIndex) {
      let middleIndex = Math.floor((rightIndex + leftIndex) / 2);
      if (arr[leftIndex] === value) {
      return leftIndex;
      }
      if (arr[rightIndex] === value) {
          return rightIndex;
      }
      if (arr[middleIndex] === value) {
          return middleIndex;
      }
      if (arr[middleIndex] < value) {
          return helper(leftIndex + 1, middleIndex);
      } else if (arr[middleIndex] > value) {
          return helper(middleIndex, rightIndex - 1);
      } else {
           return -1;
      }
  }
  return helper(leftIndex, rightIndex, value);
}

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

Binary Search - Big O Notation

• Binary Search's Big O Notation
  • O(N) ~ O(logN) => O(logN)

Naive String Search

• 긴 문자열에서 짧은 문자열을 탐색함

Naive String Search function

• 더 긴 문자열을 순회함
• 안쪽에서 더 짧은 문자열을 순회함
• 문자가 일치하지 않으면 안쪽 순회를 멈춤
• 문자가 일치하면 안쪽 순회를 계속 함
• 안쪽 순회가 완료되고 짧은 문자열이 일치하면, 일치 숫자를 증가시킴
• 일치 숫자를 반환함

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