2장 알고리즘이 중요한 까닭

알고리즘: 특정 과제를 달성하기 위해 컴퓨터에 제공되는 명령어 집합.

• 같은 과제를 둘 이상의 알고리즘으로 완수할 수 있다.

2.1 정렬된 배열

값이 항상 순서대로 있어야 하는 배열. 값을 추가할 때마다 적절한 셀에 넣어 배열의 값을 정렬된 상태로 유지한다.

정렬된 배열에 삽입할 때는 항상 실제 삽입 전에 검색을 먼저 수행해서 삽입할 올바른 위치를 정해야 한다.
배열 중간에 삽입하는 것이 최악의 시나리오이며, N+2 단계가 걸린다.

2.2 정렬된 배열의 검색

정렬된 배열에서는 값이 배열에 들어있지 않을 때 선형검색을 더 빨리 멈출 수 있다.
[3, 17, 75, 80, 202]에서 22를 찾을 경우, 75에 도달하면 더 이상 22가 오른쪽에 있을 수 없으므로 바로 검색을 중단할 수 있다.

const linearSearch = (array, searchValue) => {
  // 배열의 모든 원소를 순회한다.
  for (let i = 0; i < array.length; i++) { 
    if (array[i] === searchValue) {
      // 원하는 값을 찾으면 그 인덱스를 반환한다.
      return i;
    } else if(array[i] > searchValue) {
      // 찾고 있던 값보다 큰 원소에 도달하면 루프를 일찍 종료할 수 있다.
      break;
    }
  }
  // 배열에서 값을 찾지 못하면 null을 반환한다.
  return null;
}

linearSearch([3, 17, 75, 80, 202], 22);

하지만 찾으려는 값이 배열의 마지막 값이거나 마지막 값보다 크면 정렬되지 않은 배열과 마찬가지로 모든 셀을 검색해야 검색이 끝난다.
즉, 최악의 시나리오에선 일반적인 배열과 정렬된 배열이 효율성 면에서 차이가 없다. 두 배열 모두 N단계가 걸린다.

정렬된 배열의 장점은 선형 검색이 아닌, 다른 검색 알고리즘을 쓸 수 있다는 점이다.
이러한 알고리즘을 이진 검색이라고 부르며, 이진 검색은 선형 검색보다 훨씬 빠르다.

2.3 이진 검색

계속해서 가운데 셀을 골라 남은 수 중 반을 제거해 나가는 방법.

이진 검색은 정렬된 배열에만 쓸 수 있다. 전형적인 배열은 값의 순서가 뒤죽박죽이어서 주어진 값의 왼쪽에서 찾을지 오른쪽에서 찾을지 절대 알 수 없다.

2.3.1 코드 구현: 이진 검색

const binarySearch = (array, searchValue) => {
  // 먼저 찾으려는 값이 있을 수 있는 상한선과 하한선을 정한다.
  // 최초의 상한선은 배열의 첫 번째 값, 하한선은 마지막 값이다.
  let lowerBound = 0;
  let upperBound = array.length - 1;

  // 상한선과 하한선 사이의 가운데 값을 계속해서 확인하는 루프를 시작한다.
  while (lowerBound <= upperBound) {
    // 상한선과 하한선 사이에 중간 지점을 찾는다.
    // 책의 코드는 루비에서 결괏값이 정수가 아닐 때 가장 가까운 정수로 올림한다고 했으므로 결괏값을 가장 가까운 정수로 올림한다.
    const midpoint = Math.ceil((upperBound + lowerBound) / 2);

    // 중간 지점의 값을 확인한다.
    const valueAtMidpoint = array[midpoint];

    // 중간 지점의 값이 찾고 있던 값이면 검색을 끝낸다.
    // 그렇지 않으면 더 클지 작을지 추측한 바에 따라 상한선이나 하한선을 바꾼다.
    if (searchValue === valueAtMidpoint) {
      return midpoint;
    } else if (searchValue < valueAtMidpoint) {
      upperBound = midpoint - 1;
    } else if (searchValue > valueAtMidpoint) {
      lowerBound = midpoint + 1;
    }
  }

  // 상한선과 하한선이 같아질 때까지 경곗값을 줄였다면 찾고 있는 값이 이 배열에 없다는 의미다.
  return null;
};

binarySearch([3, 17, 75, 80, 202], 22);

만일 searchValue가 valueAtMidpoint보다 작다면, searchValue를 중간 인덱스 이전에서만 찾을 수 있다는 뜻이다. upperBound에 midpoint의 바로 왼쪽 인덱스를 할당해 검색 범위를 좁힐 수 있다.

반대로 searchValue가 valueAtMidpoint보다 크다면 searchValue를 midpoint의 오른편에서만 찾을 수 있다는 뜻이니 lowerBound에 midpoint의 바로 오른쪽 인덱스를 할당한다.

범위가 원소 0개로 좁혀지면 null을 반환한다. searchValue가 배열에 없는 것이 확실하기 때문이다.

2.4 이진 검색 대 선형 검색

작은 크기의 정렬된 배열이라면 이진 검색 알고리즘이 선형 검색 알고리즘보다 크게 나은 점이 없지만, 100개의 값을 갖는 배열에선 각각 7단계와 100단계로 단계 수가 크게 차이난다.

선형 검색에서는 배열의 원소 수를 두 배로 늘릴 때마다 검색에 필요한 단계 수도 두 배로 늘어난다.
이진 검색에서는 데이터를 두 배로 늘릴 때마다 최대 한 단계만 더 추가된다.

크기가 1,000,000개인 배열이라면 선형 검색은 최대 1,000,000단계가 걸리지만, 이진 검색은 최대 20단계면 된다.

정렬된 배열을 사용하면 삽입은 다소 느리지만, 검색은 훨씬 빠르다.

2.4.1 깜짝 퀴즈

• Q: 원소가 100개인 정렬된 배열에서 이진 검색은 7단계가 걸렸다. 원소가 200개인 정렬된 배열에서 이진 검색은 몇 단계가 걸릴까?
• A: 8단계.

이진 검색에서 데이터 크기를 두 배로 늘릴 때마다 1단계만 늘어난다. 두 배로 늘린 데이터는 첫 번째 검사에서 결국 모두 제거된다.

정렬된 배열에 삽입하는 과정은 먼저 검색을 필요로 하는데, 이 검색을 선형 검색이 아니라 이진 검색으로 하면 속도가 더 빨라질 수 있다.
물론, 일반 배열에 삽입하는 것보다는 느리다. 일반 배열에 삽입하는 것은 검색이 필요 없기 때문이다.

2.5 마무리

어떤 컴퓨팅 목표를 달성하는 방법은 대개 둘 이상 있으며, 사용자가 선택하는 알고리즘이 코드의 속도에 크게 영향을 줄 수 있다.

모든 상황에 완벽하게 들어맞는 단 하나의 자료 구조나 알고리즘은 거의 없다. 이진 검색을 쓸 수 있다고 무조건 정렬된 배열을 써야 하는 것은 아니다.