탐색 알고리즘 - 순차 탐색

순차 탐색(Sequential Search)

• 데이터가 모인 배열의 처음부터 끝까지 순서대로 비교하여 원하는 데이터를 찾아내는 알고리즘.
• 단방향으로 탐색을 수행하므로 선형 탐색(Linear Search)라고도 한다.
  
  

탐색 방법

• 자료의 집합에서 처음 원소 부터 시작하여 찾으려는 값과 일치하는지 비교한다.
• 찾는 값이 일치하는 원소를 찾으면, 그 원소가 몇 번째 원소인지를 반환한다.
• 값과 일치하는 원소가 아니라면 다음 순서의 원소를 비교하며 이 과정을 반복한다.
• 마지막 원소까지 비교하였으나 일치하는 값의 원소가 존재하지 않으면 원소가 없다고 판단한다.
  
  

특징

• 비교횟수
  최선의 경우 : 1번
  평균의 경우 : (N+1) / 2 번
  최악의 경우 : N번(배열의 크기, 즉 배열의 가장 마지막에 원소 존재하는 경우와 원소가 없는 경우)
  
  시간 복잡도 : O(n)

• 자료가 정렬되어 있지 않을 때에 사용이 가능하다.

• 적은 자료에서의 탐색이 효율적이다.

• 알고리즘이 간단하지만 속도가 느리다.

구현

function SequentialSearch(arr, data) {
  let result = -1;

  arr.forEach((d, i) => {
    if (d === data) {
      result = i + 1;
      return result;
    }
  });

  return result;
}

function Solution() {
  const arr = [23, 25, 14, 5, 66, 72, 13, 224, 51];

  const findData = 14; // 값을 변경하며 실행해보자.
  const findIdx = SequentialSearch(arr, findData);

  if (findIdx !== -1) {
    console.log(`탐색 결과 : ${findIdx}번째에 원소가 존재합니다.`);
  } else {
    console.log(`탐색 결과 : 원소가 존재하지 않습니다.`);
  }

  return;
}

Solution();