[JS 알고리즘] - 선형 검색 (Linear Search)

아래 강의를 듣고 내용을 정리한 포스트 입니다.

https://www.udemy.com/course/best-javascript-data-structures/

먼저, 여기에서 다루는 검색은 JS 의 배열 에 대한 검색 입니다.

선형 검색 (Linear Search)

아래와 같이 모든 미국의 주 이름을 담아둔 배열 데이터가 있다고 가정해 보겠습니다.
그리고 사용자가 주소를 입력해야하는 상황이라고 가정해보겠습니다. 우리는 사용자가 입력한 내용을 이 데이터 안에서 찾아야 합니다.

const US_States = [
    "Alabama", "Alaska", "Arizona", "Arkansas", "California", "Colorado", "Connecticut", "Delaware", "Florida", "Georgia",
    "Hawaii", "Idaho", "Illinois", "Indiana", "Iowa", "Kansas", "Kentucky", "Louisiana", "Maine", "Maryland",
    "Massachusetts", "Michigan", "Minnesota", "Mississippi", "Missouri", "Montana", "Nebraska", "Nevada", "New Hampshire", "New Jersey",
    "New Mexico", "New York", "North Carolina", "North Dakota", "Ohio", "Oklahoma", "Oregon", "Pennsylvania", "Rhode Island", "South Carolina",
    "South Dakota", "Tennessee", "Texas", "Utah", "Vermont", "Virginia", "Washington", "West Virginia", "Wisconsin", "Wyoming"
];

사용자가 Indiana 를 입력했다고 가정해보고, 이를 찾기 위해 가장 단순한 방법은 모든 개별항목에 대해 순서대로 찾아보는 것 입니다.
이것을 선형 검색 (Linear Search) 이라고 합니다.
자바스크립트에는 indexOf, includes, find, findIndex 같은 함수들로 선형 검색이 구현되어져 있습니다.

선형 검색의 특징

선형 검색은 첫부분에서 시작해서 끝 부분으로 이동하면서 한 번에 하나의 항목을 확인할수도 있고, 끝 부분에서 시작해서 첫 부분으로 이동할수도 있습니다.
중요한건 세트 간격으로 이동하면서 한번에 하나의 항목을 확인하는 식으로 모든 항목을 확인 한다는 것 입니다.

예제 : 12 찾기

[5, 8, 1, 100, 12, 3, 12]

 

이 숫자 배열에서 검색을 통해 12를 찾는다면, 12가 배열에 포함되는지 하나하나 검색하고 반환 값은 어느것이든 될수 있습니다.

 

선행검색 의사코드 작성해보기

1. 함수를 작성하는데 이름은 원하는대로 붙임. 배열과 값을 인수로 사용해야함

2. 전체 배열에 대한 루프를 만들고, 현재 확인중인 배열 항목이 우리가 입력하는 값과 동일한지 확인한다.

3. 동일하다면 해당 값의 인덱스를 반환하고, 끝까지 찾을수 없다면 -1 을 반환한다.

 

저는 헬퍼 메소드 재귀로 배열 안의 숫자를 찾는 선형검색을 구현 해보았습니다.

function linearSearch(list: number[], target: number) {
  let idx = list.length - 1;

  const getIndex = (rec_list: number[], target: number) => {
    if (rec_list.length <= 0) return false;

    if (rec_list[rec_list.length - 1] === target) {
      return true;
    }

    rec_list.pop();
    idx -= 1;

    return getIndex(rec_list, target);
  };

  const bool = getIndex(list, target);
  const result = bool === true ? idx : -1;
  return result;
}

뒤에서 부터 거꾸로 센것은, 앞에서 셀경우 array.shift() 를 활용해서 더 느려질수 있기 때문에 pop 을 사용하였습니다.

for 문으로 구현하면 더 간단할것 같습니다.

function linearSearch(list: number[], target: number) {
  for (let i = 0; i < list.length - 1; i++) {
    if (list[i] === target) return i;
  }
  return -1;
}

 

이렇듯, 선형검색의 시간복잡도는 O(n) 입니다.

O(n) 의 시간 복잡도는 선형 (linear) 입니다. 그렇기 때문에 선형 검색이라고 합니다.

언제 사용하는가? 

-> 데이터가 정렬되어있지 않은경우 유용.
-> 무엇인가 검색하고 탐색하기에 가장 무난한 방법이지만, O(n) 시간동안 순회하느라 입력 List 가 클수록 오래걸림