플러터 대용량 리스트 검색, indexOf를 계속 쓰면 벌어지는 일

27 January 2023

Update: 17 November 2025

플러터(Flutter)로 풍부한 기능과 대용량 데이터를 다루는 애플리케이션을 개발하다 보면, 어느 순간 발목을 잡는 성능 문제와 필연적으로 마주하게 됩니다. 사용자가 가장 직접적으로 체감하는 '느림'은 대부분 데이터 처리, 특히 수천, 수만 개의 데이터가 담긴 거대한 리스트에서 특정 항목을 찾는 작업에서 발생합니다. 우리에게 가장 친숙하고 직관적인 방법인 List.indexOf(). 하지만 이 편리함 뒤에는 대용량 데이터 앞에서 앱을 무릎 꿇게 만드는 치명적인 함정이 숨어있습니다.

List.indexOf()는 리스트의 첫 번째 요소부터 마지막 요소까지 하나씩, 모든 것을 비교하는 '선형 탐색(Linear Search)'이라는 가장 원시적인 방식으로 동작합니다. 데이터가 100개 미만일 때는 아무런 문제가 없어 보이지만, 데이터가 1,000개, 10,000개를 넘어가는 순간, 탐색 시간은 데이터 양에 정비례하여 폭발적으로 증가하며 앱의 버벅임, 심하면 ANR(Application Not Responding)을 유발하는 주범이 됩니다.

바로 이 성능 병목 현상을 해결하고 앱에 새로운 숨결을 불어넣을 강력한 무기가 Dart 팀이 직접 제공하는 공식 collection 패키지 안에 잠들어 있습니다. 그중에서도 핵심은 binarySearch 함수입니다. 이 함수는 '이진 탐색(Binary Search)'이라는 지능적인 알고리즘을 통해, 마치 마법처럼 대용량의 정렬된 리스트에서 눈 깜짝할 사이에 원하는 데이터를 찾아냅니다. 이 글에서는 binarySearch의 작동 원리부터 실전 활용법, 성능 비교, 그리고 개발자들이 흔히 저지르는 치명적인 실수까지, 여러분의 플러터 앱 성능을 극한으로 끌어올릴 모든 지식을 깊이 있게 파헤쳐 보겠습니다.

당신의 앱이 버벅이는 이유: 무심코 사용한 `indexOf`의 배신

문제 해결의 첫걸음은 문제의 정확한 인식입니다. 우리가 왜 indexOf의 사용을 경계해야 하는지, 선형 탐색의 본질을 통해 명확하게 이해해 봅시다.

선형 탐색 (Linear Search): 무식하지만 확실한, 그러나 느린 방법

선형 탐색은 가장 단순한 탐색 알고리즘입니다. 이름 그대로, 데이터가 담긴 리스트의 첫 번째(index 0) 요소부터 마지막 요소까지 순차적으로(linearly) 이동하며 찾고자 하는 값과 일치하는지 비교합니다. List.indexOf()가 바로 이 방식으로 동작합니다.

예를 들어, 10개의 숫자가 정렬된 [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] 리스트에서 72라는 값을 찾는다고 상상해 보세요. indexOf(72)는 내부적으로 다음과 같이 동작합니다.

2 == 72 인가? (아니다, 다음으로)
5 == 72 인가? (아니다, 다음으로)
8 == 72 인가? (아니다, 다음으로)
12 == 72 인가? (아니다, 다음으로)
16 == 72 인가? (아니다, 다음으로)
23 == 72 인가? (아니다, 다음으로)
38 == 72 인가? (아니다, 다음으로)
56 == 72 인가? (아니다, 다음으로)
72 == 72 인가? (찾았다! 인덱스 8을 반환.)

총 9번의 비교 연산을 통해 값을 찾아냈습니다. 만약 찾으려는 값이 91이었다면 10번 모두 비교해야 했을 것이고, 리스트에 없는 값인 100을 찾으려 했다면 역시 10번의 비교 끝에 "없음"(-1)을 반환했을 것입니다.

이러한 시간 복잡도를 컴퓨터 과학에서는 O(n)이라고 표기합니다. 여기서 'n'은 데이터의 개수를 의미하며, 최악의 경우 데이터 개수(n)만큼의 연산이 필요하다는 뜻입니다. 데이터가 100만 개라면, 최악의 경우 100만 번의 비교 연산이 필요합니다. 모바일 환경에서 이는 수십, 수백 밀리초(ms)의 지연을 의미하며, 사용자는 즉각적으로 '앱이 멈췄다'고 느끼게 됩니다.

구원투수의 등장: 이진 탐색(Binary Search)의 압도적인 효율성

이진 탐색은 선형 탐색의 무식함을 지능으로 극복합니다. 하지만 이 강력한 힘을 사용하기 위해서는 한 가지 매우 중요한 전제 조건이 필요합니다.

전제 조건: 이진 탐색은 반드시 '정렬된(Sorted)' 리스트를 대상으로만 동작합니다.

이 조건만 충족된다면, 이진 탐색은 탐색 범위를 매 단계마다 절반으로 줄여나가는 경이로운 효율성을 보여줍니다. 우리가 두꺼운 국어사전에서 '플러터'라는 단어를 찾을 때를 생각해보면 쉽습니다. 아무도 'ㄱ'부터 한 장씩 넘기지 않습니다. 일단 사전의 중간쯤을 펼쳐봅니다. 펼친 곳이 'ㅅ'이라면, 'ㅍ'은 그보다 뒤에 있을 것이므로 사전의 앞 절반은 아예 쳐다볼 필요도 없습니다. 이제 나머지 뒷부분에서 다시 중간을 펼치는 과정을 반복하며 순식간에 목표 지점에 도달합니다. 이것이 바로 이진 탐색의 핵심 원리입니다.

다시 [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] 리스트에서 72를 찾아봅시다. 이진 탐색의 과정은 다음과 같습니다.

1단계: 전체 리스트(인덱스 0~9)의 중간을 찾습니다. 중간 인덱스는 (0 + 9) / 2 = 4.5 이므로, 정수 부분인 4입니다. 인덱스 4의 값은 16입니다.
- 72는 16보다 큽니다. 따라서 우리가 찾는 값은 중간보다 오른쪽에 있을 것이 확실합니다.
- 탐색 범위를 인덱스 5~9, 즉 [23, 38, 56, 72, 91]로 좁힙니다. 왼쪽 절반은 버립니다.
2단계: 새로운 탐색 범위(인덱스 5~9)의 중간을 찾습니다. 중간 인덱스는 (5 + 9) / 2 = 7입니다. 인덱스 7의 값은 56입니다.
- 72는 56보다 큽니다. 따라서 값은 또다시 중간보다 오른쪽에 있습니다.
- 탐색 범위를 인덱스 8~9, 즉 [72, 91]로 좁힙니다.
3단계: 새로운 탐색 범위(인덱스 8~9)의 중간을 찾습니다. 중간 인덱스는 (8 + 9) / 2 = 8.5이므로, 정수 부분인 8입니다. 인덱스 8의 값은 72입니다.
- 72는 72와 같습니다. (찾았다! 인덱스 8을 반환.)

선형 탐색에서는 9번의 비교가 필요했지만, 이진 탐색은 단 3번 만에 값을 찾아냈습니다. 이 차이는 데이터가 많아질수록 기하급수적으로 벌어집니다. 이진 탐색의 시간 복잡도는 O(log n)입니다. 이는 데이터가 2배로 늘어나도 탐색 단계는 겨우 1단계만 추가된다는 의미입니다.

O(n) vs O(log n): 얼마나 큰 차이일까?

데이터 크기에 따른 최대 비교 횟수를 표로 비교해보면 그 차이가 더욱 명확하게 와닿습니다.

데이터 개수 (n)	선형 탐색 (O(n)) 최대 비교 횟수	이진 탐색 (O(log n)) 최대 비교 횟수	성능 차이 (대략)
100	100 번	7 번 (log₂100 ≈ 6.64)	약 14배
1,000	1,000 번	10 번 (log₂1000 ≈ 9.96)	약 100배
1,000,000 (백만)	1,000,000 번	20 번 (log₂1,000,000 ≈ 19.93)	약 50,000배
1,000,000,000 (십억)	1,000,000,000 번	30 번 (log₂1,000,000,000 ≈ 29.89)	약 33,000,000배

백만 개의 데이터에서 indexOf는 최악의 경우 100만 번을 비교하지만, binarySearch는 단 20번의 비교만으로 결과를 찾아냅니다. 이 정도면 단순한 성능 차이가 아니라, '가능'과 '불가능'의 차이라고 할 수 있습니다.

실전 준비: `collection` 패키지와 `binarySearch` 함수 길들이기

이제 본격적으로 플러터 프로젝트에서 binarySearch를 사용하는 방법을 단계별로 알아보겠습니다.

1단계: `collection` 패키지 추가

가장 먼저 프로젝트의 pubspec.yaml 파일에 Dart 팀이 공식적으로 관리하는 `collection` 패키지 의존성을 추가합니다.


# pubspec.yaml
dependencies:
  flutter:
    sdk: flutter
  
  # 이 줄을 dependencies 아래에 추가하세요.
  collection: ^1.18.0 # pub.dev에서 최신 버전을 확인하고 사용하세요.

파일을 저장한 후, 터미널에서 flutter pub get 명령어를 실행하거나 IDE의 패키지 가져오기 기능을 사용하여 패키지를 설치합니다. 그 다음, 사용할 Dart 파일 상단에 패키지를 import 합니다.


import 'package:collection/collection.dart';

2단계: `binarySearch` 함수 시그니처 완전 분석

binarySearch 함수의 원형은 다음과 같이 생겼습니다.


int binarySearch<E>(
  List<E> sortedList, // 1. 정렬된 리스트
  E value,             // 2. 찾고자 하는 값
  {int Function(E, E)? compare} // 3. (선택) 비교 로직을 담은 함수
)

sortedList: 탐색의 대상이 되는 리스트입니다. 매개변수 이름에 'sorted'가 명시된 것은 그만큼 정렬이 필수적이라는 점을 다시 한번 강조하는 것입니다. 정렬되지 않은 리스트를 전달하면 함수는 예측 불가능한 쓰레기 값을 반환합니다.
value: 리스트에서 찾으려는 값입니다.
compare: 두 요소를 어떻게 비교할지 정의하는 선택적 파라미터입니다. 이 함수를 제공하지 않으면, 리스트의 요소 타입 E가 기본적으로 가지고 있는 compareTo 메소드를 사용합니다. `int`, `String`, `double`과 같은 Dart의 기본 타입들은 이미 `Comparable` 인터페이스를 구현하고 있어 자체적으로 compareTo 메소드를 가지고 있으므로, 이 경우에는 `compare` 함수를 생략할 수 있습니다. 하지만 사용자가 직접 만든 커스텀 클래스(예: `User`, `Product` 모델)의 리스트를 탐색할 때는 이 `compare` 함수를 반드시 직접 구현하여 전달해야 합니다.

`compare` 함수의 3가지 규칙

compare 함수는 `(element1, element2)` 두 개의 인자를 받아 정수를 반환해야 하며, 다음 규칙을 반드시 따라야 합니다.

element1이 element2보다 작으면 (앞에 와야 하면) 음수 (보통 -1)를 반환합니다.
element1과 element2가 같으면 0을 반환합니다.
element1이 element2보다 크면 (뒤에 와야 하면) 양수 (보통 1)를 반환합니다.

이 규칙은 `List.sort`에 전달하는 비교 함수와 완전히 동일합니다. 즉, 리스트를 정렬할 때 사용한 비교 로직을 `binarySearch`의 `compare` 함수에도 동일하게 적용해야 일관성 있는 결과를 보장할 수 있습니다.

3단계: 반환 값의 비밀 - 단순한 인덱스 그 이상

많은 개발자들이 binarySearch를 처음 사용할 때 저지르는 실수는 반환 값을 indexOf와 동일하게 취급하는 것입니다. indexOf는 값이 없으면 무조건 `-1`만 반환하지만, `binarySearch`의 반환 값은 훨씬 더 많은 정보를 담고 있습니다.

값을 찾았을 경우: 해당 값의 인덱스(0 이상의 정수)를 반환합니다. 만약 리스트에 동일한 값이 여러 개 있다면, 그중 어느 것의 인덱스가 반환될지는 보장되지 않습니다.
값을 찾지 못했을 경우: 특별한 의미를 가진 음수를 반환합니다. 이 음수 값은 -(삽입점 + 1) 이라는 공식을 따릅니다.
- 여기서 '삽입점(insertion point)'이란, 찾으려던 값을 리스트에 추가하더라도 리스트의 정렬 상태가 깨지지 않는 위치(인덱스)를 의미합니다.

예를 들어, [10, 20, 40, 50] 리스트에서 30을 찾는다고 가정해 봅시다. 30은 리스트에 존재하지 않습니다.

정렬을 유지하며 30을 삽입할 위치는 20(인덱스 1)과 40(인덱스 2) 사이, 즉 인덱스 2입니다. 이것이 바로 '삽입점'입니다.
공식에 따라, binarySearch는 -(2 + 1) = -3을 반환합니다.

이 영리한 반환 값 덕분에, 우리는 단순히 값의 존재 여부만 아는 것을 넘어, 값이 없을 경우 그 값이 어디에 들어가야 하는지까지 한 번에 알 수 있습니다. 이 특징은 정렬된 리스트에 데이터를 동적으로 추가해야 하는 상황에서 매우 유용합니다.


/// 반환된 음수 값으로 삽입점을 역산하는 방법
int resultIndex = binarySearch(mySortedList, valueToFind);

if (resultIndex < 0) {
  // 값을 찾지 못했으므로, 삽입점을 계산한다.
  int insertionPoint = -resultIndex - 1;
  print('값은 없지만, 인덱스 $insertionPoint 에 삽입하면 정렬이 유지됩니다.');

  // 이 정보를 이용해 실제로 값을 삽입할 수 있다.
  mySortedList.insert(insertionPoint, valueToFind); 
  print('삽입 후 리스트: $mySortedList');
}

코드로 증명하는 `binarySearch`의 위력

이론을 마스터했으니, 이제 실제 코드를 통해 `binarySearch`를 어떻게 활용하는지 구체적인 예제와 함께 살펴보겠습니다.

예제 1: 기본 타입(int) 리스트에서 사용하기

가장 기본이 되는 정수 리스트 예제입니다. `int`는 자체적으로 `compareTo`를 가지고 있으므로 `compare` 함수를 생략할 수 있습니다.


import 'package:collection/collection.dart';

void main() {
  // 1. **반드시** 정렬된 리스트를 준비합니다.
  final numbers = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];

  // --- Case 1: 리스트에 존재하는 값(72) 찾기 ---
  int target1 = 72;
  int index1 = binarySearch(numbers, target1);
  
  print('"$target1" 찾기 결과:');
  if (index1 >= 0) {
    print('✅ 값을 찾았습니다. 인덱스: $index1, 값: ${numbers[index1]}');
  } else {
    print('❌ 값을 찾지 못했습니다.');
  }
  
  print('-' * 30);

  // --- Case 2: 리스트에 존재하지 않는 값(40) 찾기 ---
  int target2 = 40;
  int index2 = binarySearch(numbers, target2);
  
  print('"$target2" 찾기 결과:');
  if (index2 >= 0) {
    print('✅ 값을 찾았습니다. 인덱스: $index2');
  } else {
    print('❌ 값을 찾지 못했습니다. 반환된 값: $index2');
    // 반환된 음수 값으로 삽입점 계산하기
    int insertionPoint = -index2 - 1;
    print('💡 삽입 추천 위치(insertion point): $insertionPoint'); 
    // 40은 38(인덱스 6)과 56(인덱스 7) 사이에 들어가야 하므로 삽입점은 7입니다.
    // 공식에 따라 -(7 + 1) = -8 이 반환됩니다.
  }
}

/*
--- 실행 결과 ---
"72" 찾기 결과:
✅ 값을 찾았습니다. 인덱스: 8, 값: 72
------------------------------
"40" 찾기 결과:
❌ 값을 찾지 못했습니다. 반환된 값: -8
💡 삽입 추천 위치(insertion point): 7
*/

예제 2: 커스텀 객체 리스트에서 사용하기 (가장 중요한 실전 활용)

실제 플러터 앱 개발에서는 `int`나 `String` 리스트보다, 우리가 직접 정의한 모델 클래스(예: `User`, `Product`, `Post`)의 리스트를 다루는 경우가 압도적으로 많습니다. `User` 클래스 객체들의 리스트에서 특정 `id`를 가진 사용자를 초고속으로 찾는 방법을 알아보겠습니다. 이 예제에서는 `compare` 함수의 역할이 핵심입니다.


import 'package:collection/collection.dart';

// 사용자 정보를 담는 간단한 모델 클래스
class User {
  final int id;
  final String name;
  final int age;

  User({required this.id, required this.name, required this.age});

  @override
  String toString() {
    return 'User(id: $id, name: "$name", age: $age)';
  }
}

void main() {
  final users = [
    User(id: 101, name: 'Alice', age: 30),
    User(id: 451, name: 'David', age: 22),
    User(id: 500, name: 'Eve', age: 40),
    User(id: 105, name: 'Bob', age: 25),
    User(id: 230, name: 'Charlie', age: 35),
  ];

  // 1. **가장 중요한 단계**: `binarySearch`를 사용하기 전에 반드시 **탐색 기준이 되는 키(id)로 리스트를 정렬**합니다.
  users.sort((a, b) => a.id.compareTo(b.id));
  
  print('--- ID 기준 오름차순 정렬된 사용자 리스트 ---');
  users.forEach(print);
  print('-' * 20);

  // 2. 목표: id가 230인 사용자 찾기
  
  // `binarySearch`에 전달할 '찾는 값'을 대표하는 User 객체를 만듭니다.
  // `compare` 함수에서 id만 비교할 것이므로, name과 age는 어떤 값이든 상관없습니다.
  final targetUser = User(id: 230, name: 'irrelevant', age: 0);

  // 3. `compare` 함수를 직접 제공하여 id를 기준으로 비교하도록 명시합니다.
  int index = binarySearch<User>(
    users,
    targetUser,
    compare: (userA, userB) => userA.id.compareTo(userB.id),
  );

  print('id가 ${targetUser.id}인 사용자 찾기 결과:');
  if (index >= 0) {
    print('✅ 사용자를 찾았습니다!');
    print('   - 인덱스: $index');
    print('   - 사용자 정보: ${users[index]}');
  } else {
    print('❌ 해당 ID의 사용자를 찾지 못했습니다.');
    int insertionPoint = -index - 1;
    print('💡 만약 id가 ${targetUser.id}인 사용자를 추가한다면 추천 인덱스는 $insertionPoint 입니다.');
  }
}

/*
--- 실행 결과 ---
--- ID 기준 오름차순 정렬된 사용자 리스트 ---
User(id: 101, name: "Alice", age: 30)
User(id: 105, name: "Bob", age: 25)
User(id: 230, name: "Charlie", age: 35)
User(id: 451, name: "David", age: 22)
User(id: 500, name: "Eve", age: 40)
--------------------
id가 230인 사용자 찾기 결과:
✅ 사용자를 찾았습니다!
   - 인덱스: 2
   - 사용자 정보: User(id: 230, name: "Charlie", age: 35)
*/

핵심 포인트: 위 예제에서 compare: (userA, userB) => userA.id.compareTo(userB.id) 코드가 핵심입니다. 이 코드는 "두 User 객체를 비교할 때, 다른 필드는 모두 무시하고 오직 id 필드의 대소 관계만으로 판단하겠다"는 규칙을 `binarySearch`에게 알려주는 역할을 합니다. 덕분에 targetUser 객체의 name이나 age 값에 신경 쓸 필요 없이, 오직 `id` 값만으로 효율적인 탐색이 가능해집니다.

숫자는 거짓말하지 않는다: `indexOf` vs `binarySearch` 성능 벤치마크

이론적으로 이진 탐색이 빠르다는 것은 알겠습니다. 그렇다면 실제 플러터/Dart 환경에서 체감 성능은 얼마나 차이가 날까요? `Stopwatch` 클래스를 사용하여 직접 성능을 측정하고 그 결과를 눈으로 확인해 보겠습니다.

테스트 시나리오: 100만 개의 정수 요소를 가진 정렬된 리스트를 생성하고, 리스트의 거의 맨 끝에 있는 값(999,999)을 찾는 상황을 가정합니다. 이 시나리오는 indexOf에게는 거의 최악의 조건입니다.


import 'dart:math';
import 'package:collection/collection.dart';

void main() {
  final int listSize = 1000000; // 백만 개
  final int targetValue = 999999; // 찾을 값 (거의 마지막에 위치하여 선형 탐색에 불리)

  // 1. 백만 개의 연속된 정수를 가진 리스트 생성.
  // List.generate는 이미 [0, 1, 2, ..., 999999] 로 정렬된 리스트를 만듭니다.
  final List<int> largeList = List.generate(listSize, (index) => index);

  final stopwatch = Stopwatch();

  // --- 테스트 1: List.indexOf() (선형 탐색) ---
  stopwatch.start();
  final int indexByIndexOf = largeList.indexOf(targetValue);
  stopwatch.stop();
  final linearSearchTime = stopwatch.elapsedMicroseconds;
  
  print('--- 🐌 선형 탐색 (indexOf) ---');
  print('찾은 인덱스: $indexByIndexOf');
  print('걸린 시간: ${linearSearchTime.toString().padLeft(6)} µs (마이크로초)');
  
  stopwatch.reset();

  // --- 테스트 2: binarySearch() (이진 탐색) ---
  stopwatch.start();
  final int indexByBinarySearch = binarySearch(largeList, targetValue);
  stopwatch.stop();
  final binarySearchTime = stopwatch.elapsedMicroseconds;

  print('\n--- 🚀 이진 탐색 (binarySearch) ---');
  print('찾은 인덱스: $indexByBinarySearch');
  print('걸린 시간: ${binarySearchTime.toString().padLeft(6)} µs (마이크로초)');

  print('\n--- 📊 결과 분석 ---');
  if (binarySearchTime > 0) {
    final double ratio = linearSearchTime / binarySearchTime;
    print('결론: binarySearch가 indexOf보다 약 ${ratio.toStringAsFixed(1)}배 빠릅니다.');
  } else {
    print('결론: binarySearch가 너무 빨라 측정 시간이 0에 가깝습니다. 비교 불가!');
  }
}

실행 결과 (PC 환경에 따라 다소 차이가 있을 수 있습니다)

--- 🐌 선형 탐색 (indexOf) ---
찾은 인덱스: 999999
걸린 시간:  18452 µs (마이크로초)

--- 🚀 이진 탐색 (binarySearch) ---
찾은 인덱스: 999999
걸린 시간:      3 µs (마이크로초)

--- 📊 결과 분석 ---
결론: binarySearch가 indexOf보다 약 6150.7배 빠릅니다.

결과는 충격적입니다. indexOf가 약 18.5 밀리초(ms)가 걸린 반면, binarySearch는 단 0.003 밀리초(ms) 만에 작업을 완료했습니다. 이 테스트에서는 6,000배 이상의 압도적인 성능 차이를 보여주었습니다. 데이터의 양이 수백만, 수천만 개로 늘어난다면 이 격차는 상상을 초월할 정도로 벌어질 것입니다. 사용자 목록, 상품 목록, 실시간 채팅 메시지 등 대용량 데이터를 다루는 현대적인 앱에서 binarySearch의 도입은 더 이상 선택이 아닌 '필수'라고 할 수 있습니다.

`binarySearch`의 숨겨진 조력자, `lowerBound`

collection 패키지에는 `binarySearch`와 매우 유사하지만 목적이 약간 다른 `lowerBound`라는 유용한 함수도 포함되어 있습니다. `binarySearch`가 '값을 찾는 것'에 초점이 맞춰져 있다면, `lowerBound`는 '정렬을 유지하기 위한 삽입 위치를 찾는 것'에 특화되어 있습니다.


int lowerBound<E>(
  List<E> sortedList,
  E value,
  {int Function(E, E)? compare}
)

`lowerBound`는 리스트에서 `value`와 같거나 큰 첫 번째 요소의 인덱스를 반환합니다. 즉, 삽입점(insertion point)을 항상 직접적으로 반환합니다.

binarySearch: 값이 없을 때 -(insertionPoint + 1)을 반환하므로, 삽입점을 알려면 -index - 1 계산이 필요합니다.
lowerBound: 값이 있든 없든 항상 삽입점 인덱스를 직접 반환합니다.

예를 들어, 중복된 값이 있는 [10, 20, 30, 30, 40] 리스트에서 `lowerBound`를 사용해 봅시다.

lowerBound(list, 30): 리스트에서 30과 같거나 큰 첫 번째 요소는 인덱스 2에 있는 `30`입니다. 따라서 2를 반환합니다.
lowerBound(list, 25): 25는 리스트에 없습니다. 25보다 큰 첫 번째 요소는 인덱스 2의 `30`입니다. 따라서 삽입점인 2를 반환합니다.
lowerBound(list, 50): 50은 리스트의 모든 요소보다 큽니다. 따라서 맨 끝에 삽입해야 할 위치인 리스트의 길이(5)를 반환합니다.

따라서, 값의 존재 여부 확인이 아니라 정렬된 리스트에 새 데이터를 '삽입할 위치'를 찾는 것이 주된 목적이라면, binarySearch의 반환 값을 변환하는 것보다 `lowerBound`를 사용하는 것이 코드의 의도를 더 명확하게 드러내고 가독성을 높일 수 있습니다.

이것만은 피하세요: `binarySearch` 사용 시 흔한 함정 3가지

`binarySearch`는 강력한 도구이지만, 올바르게 사용하지 않으면 예상치 못한 버그의 원인이 될 수 있습니다.

함정 1. 가장 치명적인 실수: 정렬되지 않은 리스트 사용

수없이 강조했지만 가장 흔하게 발생하는 문제입니다. 이진 탐색 알고리즘의 대전제는 '정렬'입니다. 만약 정렬되지 않은 리스트를 `binarySearch`에 전달하면 함수는 에러를 발생시키지 않고, 그저 아무 의미 없는 엉뚱한 음수 값이나 잘못된 인덱스를 반환할 뿐입니다. 디버깅이 매우 어려워지므로 항상 `binarySearch` 호출 직전에 리스트가 의도한 기준으로 정렬되어 있는지 반드시 확인해야 합니다. 서버에서 받은 데이터가 정렬을 보장하지 않는다면, 클라이언트에서 반드시 list.sort()를 먼저 호출해야 합니다.

함정 2. `compare` 함수와 정렬 로직의 불일치

커스텀 객체를 다룰 때, 리스트를 정렬할 때 사용한 비교 로직과 `binarySearch`의 `compare` 함수에 전달한 로직이 서로 다른 경우 문제가 발생합니다. 예를 들어, 리스트는 `User`의 `age`로 정렬해놓고, `binarySearch`에서는 `id`를 기준으로 찾으려고 하면 당연히 잘못된 결과를 반환합니다. 항상 정렬 기준과 탐색 기준은 동일해야 합니다.

함정 3. `binarySearch`가 만능이 아닐 때

모든 상황에서 `binarySearch`가 정답은 아닙니다. 다음의 경우에는 다른 접근법을 고려하는 것이 좋습니다.

리스트가 매우 작을 때: 데이터가 수십 개 정도로 적다면 indexOf와 성능 차이가 거의 없습니다. 이 경우 `binarySearch`를 위해 굳이 정렬을 하거나 코드를 복잡하게 만들 필요 없이 간단한 `indexOf`가 더 나은 선택일 수 있습니다.
정렬 비용이 검색 이득보다 클 때: 데이터 검색 빈도보다 추가/삭제/수정이 훨씬 더 잦아서 매번 리스트 전체를 다시 정렬해야 한다면, 정렬에 드는 O(n log n)의 비용이 이진 탐색으로 얻는 O(log n)의 이득보다 커질 수 있습니다.
이런 경우에는 데이터의 특성에 따라 Map이나 HashSet과 같은 다른 자료구조를 사용하는 것이 훨씬 효율적입니다. 예를 들어, 고유한 ID로 객체를 찾아야 하는 경우 Map를 사용하면 평균 O(1)의 시간 복잡도로, 즉 데이터 양에 상관없이 거의 즉시 탐색이 가능합니다.

결론: 현명한 개발자의 선택, `binarySearch`로 앱 성능을 구출하라

지금까지 플러터의 `collection` 패키지가 제공하는 강력한 성능 최적화 도구, `binarySearch`에 대해 깊이 있게 탐험했습니다. 단순히 느린 부분을 개선하는 것을 넘어, 데이터 구조와 알고리즘의 중요성을 다시 한번 깨닫는 계기가 되었을 것입니다.

오늘의 핵심 요약:

indexOf (선형 탐색, O(n))는 데이터가 많아지면 앱 성능에 치명적일 수 있다.
binarySearch (이진 탐색, O(log n))는 정렬된 리스트에서 압도적으로 빠른 검색 속도를 보장한다.
사용 전 반드시 리스트를 정렬해야 하며, 이는 `binarySearch` 사용의 제1원칙이다.
커스텀 객체를 검색할 때는 `compare` 함수를 통해 정렬 기준과 동일한 비교 기준을 명확히 지정해야 한다.
값을 찾지 못했을 때 반환되는 음수 값(-(insertion point + 1))을 통해 값이 삽입될 위치까지 알 수 있다. 이 목적에는 `lowerBound` 함수가 더 직관적일 수 있다.
데이터의 추가/삭제가 매우 빈번하다면 정렬 비용을 고려하여 `Map`과 같은 다른 자료구조를 검토해야 한다.

만약 지금 여러분의 플러터 애플리케이션 어딘가에서 대용량 데이터를 다루며 `List.indexOf()`나 `List.where().first` 같은 코드를 무심코 사용하고 있다면, 지금 바로 `binarySearch`로 교체하는 것을 고려해 보세요. 이 작은 변화 하나만으로도 사용자는 이전과는 비교할 수 없이 쾌적하고 빠른 앱을 경험하게 될 것입니다. `collection` 패키지에는 이 외에도 `groupBy`, `mergeSort`, `DeepCollectionEquality` 등 개발을 윤택하게 해주는 주옥같은 유틸리티가 많이 포함되어 있으니, 이번 기회에 공식 문서를 함께 살펴보시는 것을 강력히 추천합니다.

collection 패키지 dart ko 이진 탐색 플러터 성능 최적화