원하는 값, 어떻게 찾을까?

🔎 탐색(Search) = 원하는 값이 어디 있나 찾기 탐색은 여러 데이터 중에서 특정 값이 있는지, 있다면 어디에 있는지를 찾아내는 일이에요. 배열에서 42라는 값을 찾거나, 그 값의 인덱스를 알아내는 상황이죠. 💡 도서관에서 책 한 권을 찾는다고 생각해봐요. 책장을 처음부터 하나씩 보는 방법(선형)과, 정렬된 목록에서 중간을 펼쳐 좁혀가는 방법(이진)이 있어요.

🚶 하나씩 순회하며 비교

function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {  // 앞에서부터 하나씩
    if (arr[i] === target) {
      return i;      // 찾으면 그 위치(인덱스) 반환
    }
  }
  return -1;         // 끝까지 없으면 -1
}

linearSearch([7, 2, 9, 4], 9);  // → 2

찾는 값이 맨 끝에 있거나 아예 없으면 배열 전체를 다 훑어야 해요. 그래서 최악의 경우 비교 횟수는 n번 → O(n). 💡 정렬 여부와 무관하게 항상 동작하지만, n이 크면 느려요. "정렬 안 된 데이터에서 한 번만 찾을 때"엔 오히려 이게 정답이에요.

✂️ 동작 원리 — low · high · mid 1. 범위의 양 끝 low(왼쪽), high(오른쪽)를 잡아요.
2. 가운데 mid를 구해 arr[mid]와 target을 비교해요.
3. target이 더 크면 왼쪽 절반을 버리고(low = mid + 1), 더 작으면 오른쪽 절반을 버려요(high = mid - 1).
4. 같으면 찾은 거예요. 범위가 빌 때까지 반복해요.

✂️ 코드로 보기

function binarySearch(arr, target) {  // arr은 오름차순 정렬 가정
  let low = 0, high = arr.length - 1;
  while (low <= high) {
    let mid = Math.floor((low + high) / 2);  // 가운데 인덱스
    if (arr[mid] === target) {
      return mid;                 // 찾음
    } else if (arr[mid] < target) {
      low = mid + 1;              // 오른쪽 절반만 남김
    } else {
      high = mid - 1;             // 왼쪽 절반만 남김
    }
  }
  return -1;                      // 없음
}

binarySearch([1, 3, 5, 7, 9, 11], 9);  // → 4

💡 한 번 비교할 때마다 후보가 절반으로 줄어요. 그래서 아무리 커도 몇 번이면 끝나요.

🧰 언제 무엇을 쓰나 선형 탐색 — 데이터가 정렬돼 있지 않고, 탐색을 몇 번 안 할 때. 단순하고 전제조건이 없어요.
이진 탐색 — 데이터가 이미 정렬돼 있거나, 한 번 정렬해두고 여러 번 탐색할 때. 정렬 비용을 여러 탐색이 나눠 부담하니 압도적으로 유리해요. 💡 "정렬 비용은 한 번, 빠른 탐색은 여러 번" — 이 구조일수록 이진 탐색의 이득이 커져요.