[알고리즘] 선형검색, 이진검색

1. 선형검색

선형검색은 처음부터 끝까지 한번에 하나씩 검색하는 것이다.

indexOf, includes, find, findIndex 등이 있다.

시간복잡도 : O(n)

 

(문제)

arr, num 2개의 매개변수가 주어지는데 arr안에 num가 있다면 인덱스 추출

num가 없다면 -1 return

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

 

(코드)

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

2. 이진검색

이진 검색이란 중간값과 찾으려는 값을 비교하고 값이 있을 범위를 새로 정한후 반복하는것이다.

중간점을 기준으로 좌측절반과 우측절반중 어디쪽에 있는지 확인 후 다시 찾는 것이다.

선형검색보다 빠르다는 장점이 있지만 값이 순서대로 분류가 되어있지 않다면 사용할수 없다.

 

(문제)

배열안에 값이 있다면 해당 인덱스 return, 없다면 -1 return

console.log(binarySearch([1, 2, 3, 4, 5], 2)); // 1
console.log(binarySearch([1, 2, 3, 4, 5], 3)); // 2
console.log(binarySearch([1, 2, 3, 4, 5], 5)); // 4
console.log(binarySearch([1, 2, 3, 4, 5], 6)); // -1
console.log(
  binarySearch(
  [5, 6, 10, 13, 14, 18, 30, 34, 35, 37, 40, 44, 64, 79, 84, 86, 95, 96, 98, 99], 10
  )
); // 2
console.log(
  binarySearch(
    [ 5, 6, 10, 13, 14, 18, 30, 34, 35, 37, 40, 44, 64, 79, 84, 86, 95, 96, 98, 99 ], 95
  )
); // 16
console.log(
  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 index = 0;
  if (arr[start] > num || arr[end] < num) return -1;
  while (start !== end) {
    index = Math.floor((start + end) / 2);
    if (arr[index] === num) {
      return index;
    } else if (arr[index + 1] === num) {
      return index + 1;
    } else if (arr[index] < num) {
      start = index;
    } else {
      end = index;
    }
  }
  return -1;
}

(리팩터링)

function binarySearch(arr, num) {
  let start = 0;
  let end = arr.length - 1;
  let index = Math.floor((start + end) / 2);
  while (start <= end) {
    if (arr[index] === num) return index;
    if (arr[index] < num) start = index + 1;
    if (arr[index] > num) end = index - 1;
    index = Math.floor((start + end) / 2);
  }
  return -1;
}

3. 나이브 문자열 검색

찾으려는 문자열과 한글자씩 대조해보면서 찾는 알고리즘이다.

 

(문제)

두개의 string이 주어지는 데 str1안에 str2가 몇개 포함되어있는지 확인하는 함수

console.log(naiveSearch("lorie loled", "lol")); //1

(코드)

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