순차 탐색

패스트 캠퍼스 코딩테스느 강좌, 잔재미코딩 님의 수업을 참고했습니다.

순차 탐색

• 탐색: 여러 데이터 중에서 원하는 데이터를 찾아내는 것
• 순차 탐색: 데이터가 담겨 있는 배열을 앞에서부터 하나씩 비교하여 원하는 데이터를 찾는 방법

구현

const data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

// arr속에서 target을 찾는다.
const sequencialSearch = (arr, target) => {
  for (let i = 0; i < arr.length; i++) {
    // 해당 값의 인덱스 return
    if (arr[i] == target) {
      return i;
    }
  }
  // arr 안에 target이 없다면
  return -1;
};

console.log(sequencialSearch(data, 5)); // 4 반환
console.log(sequencialSearch(data, 11)); // -1 반환

시간 복잡도

최악의 경우 배열의 길이가 n일 때, n번 찾아야 한다.

O(n²)