선형 탐색과 이진 탐색 비교: JavaScript에서 언제 무엇을 사용할까?

선형 탐색과 이진 탐색은 데이터를 찾는 대표적인 탐색 알고리즘입니다. 선형 탐색은 배열의 앞에서부터 하나씩 값을 확인하며 목표 값을 찾는 방식입니다. 데이터가 정렬되어 있지 않아도 사용할 수 있고, 구현이 단순해 JavaScript에서 매우 자주 사용됩니다. 반면 이진 탐색은 정렬된 배열에서 중앙값을 확인하고 탐색 범위를 절반씩 줄이며 목표 값을 찾는 방식입니다. 조건은 더 까다롭지만 대량 데이터에서는 훨씬 빠르게 동작할 수 있습니다.

JavaScript 실무에서는 includes(), find(), findIndex(), filter() 같은 표준 메서드를 사용해 탐색하는 경우가 많습니다. 이 메서드들은 주로 선형 탐색과 가까운 개념으로 이해할 수 있습니다. 이진 탐색은 일반 UI 코드에서 매일 직접 작성되는 경우는 적지만, 정렬된 큰 데이터를 반복 검색하거나 알고리즘 문제를 해결할 때 매우 중요합니다. 이 글에서는 두 탐색 방식의 조건, 동작 방식, 시간 복잡도, 코드 예제, 장단점과 사용 기준을 비교합니다.

1. 선형 탐색과 이진 탐색 개요

선형 탐색은 데이터를 처음부터 끝까지 순서대로 확인합니다. 목표 값을 찾으면 결과를 반환하고, 끝까지 찾지 못하면 실패를 의미하는 값을 반환합니다. 정렬이 필요 없고 어떤 순서의 데이터에도 사용할 수 있어 매우 유연합니다. 예를 들어 [5, 3, 8, 1]에서 8을 찾는다면 5, 3, 8 순서로 확인하고 탐색을 종료합니다.

이진 탐색은 정렬된 데이터에서만 사용할 수 있습니다. 오름차순 배열에서 중앙값을 확인하고, 목표 값이 중앙값보다 작으면 왼쪽, 크면 오른쪽만 탐색합니다. 매번 절반의 범위를 버릴 수 있으므로 탐색 횟수가 크게 줄어듭니다. 따라서 정렬된 대량 데이터에서는 이진 탐색이 선형 탐색보다 훨씬 효율적입니다.

1.1 선형 탐색의 특징

선형 탐색은 전제 조건이 거의 없습니다. 배열이 정렬되어 있지 않아도 되고, 숫자뿐 아니라 문자열, 객체, 복합 조건에도 적용할 수 있습니다. JavaScript의 find()나 filter()와도 잘 맞습니다.

단점은 데이터가 많아질수록 느려질 수 있다는 것입니다. 목표 값이 마지막에 있거나 존재하지 않으면 전체 요소를 확인해야 하므로 시간 복잡도는 O(n)입니다.

1.2 이진 탐색의 특징

이진 탐색은 정렬된 데이터에서 매우 빠릅니다. 시간 복잡도는 O(log n)이며, 데이터 수가 커져도 비교 횟수가 천천히 증가합니다. 대량의 정렬 배열을 반복 검색할 때 효과적입니다.

하지만 데이터가 반드시 정렬되어 있어야 하고, left, right, mid의 경계 처리를 정확히 해야 합니다. 구현 난이도는 선형 탐색보다 높습니다.

2. 사용 조건의 차이

선형 탐색과 이진 탐색의 가장 큰 차이는 사용 조건입니다. 선형 탐색은 데이터 순서에 상관없이 사용할 수 있습니다. API에서 받은 원본 순서, 사용자 입력 순서, 등록순, 표시순 등 어떤 순서의 배열에서도 그대로 동작합니다. 정렬이나 전처리가 필요 없기 때문에 사용하기 쉽습니다.

이진 탐색은 데이터가 정렬되어 있어야 합니다. 오름차순이든 내림차순이든 일정한 규칙으로 정렬되어 있어야 중앙값을 기준으로 어느 절반을 버릴지 판단할 수 있습니다. 정렬되어 있지 않은 데이터에서는 이진 탐색을 사용할 수 없습니다.

2.1 선형 탐색은 미정렬 데이터에서도 가능하다

선형 탐색은 미정렬 데이터에서 그대로 사용할 수 있습니다. 예를 들어 상품 목록이 등록순으로 정렬되어 있거나, 사용자 목록이 최근 업데이트순으로 정렬되어 있어도 조건에 맞는 데이터를 앞에서부터 찾을 수 있습니다.

이 점 때문에 실무에서는 선형 탐색 계열의 메서드가 많이 사용됩니다. 데이터의 원래 순서를 유지해야 하는 경우에도 안전합니다.

2.2 이진 탐색은 정렬 데이터가 필요하다

이진 탐색은 정렬된 데이터가 필요합니다. 정렬되어 있어야 중앙값보다 작은 값이 왼쪽에 있고 큰 값이 오른쪽에 있다는 판단을 할 수 있습니다.

정렬되지 않은 데이터를 이진 탐색하려면 먼저 정렬해야 합니다. 그러나 정렬 비용이 있으므로, 한 번만 검색한다면 선형 탐색이 더 나을 수 있습니다. 이진 탐색은 정렬된 데이터를 여러 번 검색할 때 특히 유리합니다.

3. 동작 방식의 차이

선형 탐색은 한 단계씩 이동합니다. 첫 번째 요소를 확인하고, 아니면 두 번째 요소를 확인하고, 다시 세 번째 요소를 확인합니다. 매우 직관적이며 코드도 단순합니다. 조건에 맞는 요소를 찾으면 멈출 수 있지만, 찾지 못하면 끝까지 확인해야 합니다.

이진 탐색은 중앙에서 시작합니다. 중앙값과 목표 값을 비교한 뒤, 목표 값이 있을 수 없는 절반을 버립니다. 이렇게 남은 범위에서 다시 중앙을 확인합니다. 이 방식은 선형 탐색보다 복잡하지만, 큰 데이터에서 훨씬 적은 비교로 값을 찾을 수 있습니다.

3.1 선형 탐색의 동작

예를 들어 [2, 9, 4, 7]에서 7을 찾는다면 2, 9, 4, 7을 순서대로 확인합니다. 목표 값이 마지막에 있으므로 네 번의 비교가 필요합니다.

목표 값이 첫 번째에 있으면 한 번으로 끝나지만, 존재하지 않으면 모든 요소를 확인해야 합니다. 단순하지만 데이터가 많을수록 비용이 커집니다.

3.2 이진 탐색의 동작

예를 들어 [1, 3, 5, 7, 9, 11, 13]에서 11을 찾는다면 먼저 중앙값 7을 확인합니다. 11은 7보다 크므로 오른쪽 절반만 탐색합니다. 다음 중앙값을 확인하면 더 적은 단계로 11에 도달할 수 있습니다.

이처럼 이진 탐색은 매번 절반을 버립니다. 데이터가 많을수록 이 장점이 커집니다.

4. 시간 복잡도 비교

선형 탐색의 시간 복잡도는 O(n)입니다. 데이터가 n개일 때, 최악의 경우 n개 모두를 확인해야 합니다. 목표 값이 앞쪽에 있으면 빠르지만, 뒤쪽에 있거나 존재하지 않으면 오래 걸릴 수 있습니다. 데이터 수에 비례해 처리량이 증가합니다.

이진 탐색의 시간 복잡도는 O(log n)입니다. 한 번 비교할 때마다 탐색 범위가 절반으로 줄어들기 때문입니다. 데이터가 두 배가 되어도 비교 횟수는 대략 한 번만 늘어납니다. 이 차이는 대량 데이터에서 매우 크게 나타납니다.

4.1 O(n)의 의미

O(n)은 입력 크기에 비례해 작업량이 증가한다는 뜻입니다. 10개면 최대 10번, 1000개면 최대 1000번, 100만 개면 최대 100만 번 가까이 확인할 수 있습니다.

선형 탐색이 이 특성을 가집니다. 작은 데이터에서는 충분하지만, 큰 데이터를 반복 검색하면 부담이 커질 수 있습니다.

4.2 O(log n)의 의미

O(log n)은 입력 크기가 증가해도 작업량이 매우 천천히 증가한다는 뜻입니다. 이진 탐색은 매번 범위를 절반으로 줄이기 때문에 이런 특성을 가집니다.

정렬된 큰 데이터에서 이진 탐색은 매우 효율적입니다. 하지만 정렬 조건이 필요하고, 정렬 비용도 함께 고려해야 합니다.

5. JavaScript 코드 비교

JavaScript에서 선형 탐색은 for문으로 쉽게 구현할 수 있습니다. 실무에서는 includes(), find(), findIndex() 같은 표준 메서드를 사용하는 경우가 많습니다. 코드가 짧고 의도가 명확하다는 장점이 있습니다.

이진 탐색은 left, right, mid를 관리해야 하기 때문에 코드가 조금 더 복잡합니다. 하지만 정렬된 데이터에서는 훨씬 빠르게 동작할 수 있습니다. 아래 예제는 두 방식 모두 목표 값의 인덱스를 반환하고, 찾지 못하면 -1을 반환합니다.

5.1 선형 탐색 코드

function linearSearch(array, target) {
  for (let i = 0; i < array.length; i++) {
    if (array[i] === target) {
      return i;
    }
  }

  return -1;
}

console.log(linearSearch([1, 3, 5, 8, 10], 8)); // 3

선형 탐색은 정렬되지 않은 배열에서도 사용할 수 있습니다. 구현이 간단하고 이해하기 쉽습니다.

5.2 이진 탐색 코드

function binarySearch(array, target) {
  let left = 0;
  let right = array.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (array[mid] === target) {
      return mid;
    }

    if (array[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1;
}

console.log(binarySearch([1, 3, 5, 8, 10], 8)); // 3

이진 탐색은 오름차순으로 정렬된 배열을 전제로 합니다. 미정렬 배열에는 사용할 수 없습니다.

6. 선형 탐색을 사용해야 하는 경우

선형 탐색은 데이터가 작거나, 정렬되어 있지 않거나, 검색 조건이 복잡한 경우에 적합합니다. JavaScript 실무에서는 객체 배열에서 조건에 맞는 요소를 찾는 작업이 많기 때문에 find()나 filter()를 사용하는 선형 탐색 방식이 자연스럽습니다. 코드가 짧고 읽기 쉽다는 점도 큰 장점입니다.

또한 한 번만 검색하는 경우에도 선형 탐색이 충분한 경우가 많습니다. 이진 탐색을 위해 데이터를 먼저 정렬하는 비용을 생각하면, 미정렬 데이터를 그대로 탐색하는 편이 더 효율적일 수 있습니다.

6.1 조건이 복잡한 경우

객체 배열에서 여러 조건을 조합해 검색해야 한다면 선형 탐색이 더 적합합니다.

const user = users.find(item => item.role === "admin" && item.active);

이런 조건은 정렬된 단일 기준을 전제로 하는 이진 탐색과 잘 맞지 않습니다. 복잡한 조건 검색에는 선형 탐색이 더 자연스럽습니다.

6.2 데이터가 작은 경우

데이터가 작다면 선형 탐색으로 충분합니다. 10개, 20개 정도의 배열에 이진 탐색을 구현하는 것은 과한 최적화일 수 있습니다.

실무에서는 성능보다 가독성과 유지보수가 더 중요한 경우가 많습니다. 작은 데이터에는 표준 메서드를 사용한 단순한 구현이 적합합니다.

7. 이진 탐색을 사용해야 하는 경우

이진 탐색은 데이터가 정렬되어 있고, 데이터가 크며, 검색이 반복되는 경우에 적합합니다. 예를 들어 오름차순으로 정렬된 ID 목록에서 특정 ID를 여러 번 찾는 경우, 이진 탐색은 선형 탐색보다 훨씬 효율적일 수 있습니다.

또한 이진 탐색은 특정 값과 완전히 일치하는 요소를 찾는 것뿐 아니라, 경계 값을 찾는 문제에도 유용합니다. 예를 들어 특정 값 이상이 되는 첫 번째 위치를 찾거나, 조건을 만족하는 최소값을 찾을 때 활용할 수 있습니다.

7.1 정렬 데이터를 반복 검색하는 경우

이미 정렬된 데이터에서 여러 번 검색한다면 이진 탐색이 효과적입니다. 숫자 ID, 시간순 데이터, 점수순 데이터처럼 정렬 상태가 유지되는 데이터에 적합합니다.

다만 데이터가 자주 추가되거나 삭제되어 정렬 상태를 유지하기 어렵다면, 정렬 유지 비용도 고려해야 합니다. 전체 워크플로를 기준으로 판단해야 합니다.

7.2 경계 탐색이 필요한 경우

이진 탐색은 특정 값 이상이 되는 첫 번째 위치, 특정 조건을 만족하는 최소값 같은 경계 탐색에 유용합니다. 이런 문제는 선형 탐색으로도 해결할 수 있지만, 데이터가 크면 이진 탐색이 더 효율적입니다.

경계 탐색은 기본 이진 탐색보다 조금 더 어렵지만, 알고리즘 이해를 확장하는 데 매우 중요합니다.

8. 비교표로 정리하기

선형 탐색과 이진 탐색의 차이를 표로 정리하면 선택 기준이 더 명확해집니다. 선형 탐색은 조건이 적고 구현이 쉽지만, 큰 데이터에서는 느릴 수 있습니다. 이진 탐색은 정렬된 데이터가 필요하지만, 조건이 맞으면 매우 빠르게 동작합니다.

실무에서는 먼저 표준 메서드로 단순하게 작성하고, 데이터 크기나 검색 횟수가 문제가 될 때 이진 탐색, Map, Set 같은 방법을 고려하는 것이 현실적입니다.

8.1 비교표

8.2 표에서 알 수 있는 점

선형 탐색은 유연하고 단순합니다. 정렬되지 않은 데이터, 작은 데이터, 복잡한 조건 검색에 잘 맞습니다. JavaScript의 표준 메서드와도 자연스럽게 연결됩니다.

이진 탐색은 조건이 맞을 때 매우 빠릅니다. 정렬된 대량 데이터를 반복적으로 검색하는 상황에서 강력합니다. 두 알고리즘 중 하나가 항상 더 좋은 것은 아니며, 데이터 상태와 사용 목적에 맞게 선택해야 합니다.

마치며

선형 탐색과 이진 탐색은 모두 중요한 탐색 알고리즘입니다. 선형 탐색은 데이터를 앞에서부터 순서대로 확인하는 단순한 방식이며, 정렬되지 않은 데이터에도 사용할 수 있습니다. 구현이 쉽고 JavaScript의 find(), includes(), filter() 같은 메서드와도 밀접하게 관련됩니다. 이진 탐색은 정렬된 데이터에서 중앙값을 기준으로 탐색 범위를 절반씩 줄이는 방식이며, O(log n)의 시간 복잡도로 대량 데이터에서 매우 효율적입니다.

두 방식의 핵심 차이는 유연성과 속도입니다. 선형 탐색은 조건이 적고 다양한 상황에서 사용할 수 있지만, 데이터가 많아지면 느려질 수 있습니다. 이진 탐색은 빠르지만 정렬된 데이터가 필요하고 경계 처리를 정확히 해야 합니다. 작은 배열이나 복잡한 조건 검색에는 선형 탐색이 적합하고, 정렬된 대량 데이터를 반복 검색해야 한다면 이진 탐색이 적합합니다.

JavaScript 실무에서는 먼저 읽기 쉬운 표준 메서드를 사용하는 것이 기본입니다. 성능 문제가 실제로 발생하면 탐색이 병목인지 측정하고, 필요에 따라 Map, Set, 이진 탐색, 서버 측 검색을 검토하는 것이 좋습니다. 선형 탐색과 이진 탐색의 차이를 이해하면 데이터 검색을 더 효율적으로 설계할 수 있습니다.