검색(Search) 알고리즘은 저장된 데이터 중에서 원하는 값을 찾아내는 방법

1. 선형 탐색 (Linear Search)

• 데이터를 처음부터 끝까지 순차적으로 확인하며 목표 값을 찾는 방식.

• 정렬되지 않은 데이터에서도 사용 가능.

• 언제? 데이터가 작거나, 정렬되지 않아서 간단히 훑어야 할 때

• 포인트: 구현이 가장 쉽지만 최악/평균 O(n)

• 적용 구조: 배열(Array), 연결리스트(Linked List)

• 원리: 처음부터 끝까지 하나씩 비교

// [Linear Search] 앞에서부터 차례대로 비교해 찾는다: O(n)
function linearSearch(arr, target) {
for (let i = 0; i < arr.length; i++) if (arr[i] === target) return i;
return -1;
}

// demo
console.log(linearSearch([7, 3, 9, 2], 9)); // 2
console.log(linearSearch([7, 3, 9, 2], 5)); // -1 (없음)

2. 이진 탐색 (Binary Search)

• 데이터를 정렬된 상태에서 탐색 범위를 절반씩 줄여나가며 목표 값을 찾는 알고리즘.

• 언제? 정렬된 배열에서 매우 효율적

• 포인트: 정렬이 필수, 인덱스 기반 구조에 적합

• 원리: 중간값과 비교하여 절반씩 범위를 줄임

• 시간 복잡도: O(log n)

• 예시 코드