[Algorithm] 선형 탐색, 분할 정복, 이진 탐색(Binary Search)

선형 탐색,  순차 탐색 (Linear Search, Sequential Search)

• 정렬된 배열 안에서 특정 원소를 찾기 위해 인덱스 0부터 차례로 탐색
• 원소를 건너뛰는 일 없이 순차적으로 탐색
• 선형 탐색을 이용해 O(n)의 시간복잡도로 구현할 수 있다.

const arr = [1, 2, 3, 4, 5, 6];

const linearSearch = (sortedIntArray, value) => {
  for (let i = 0; i < arr.length; i++){
    if (arr[i] === value)
      return i;
  }
  return -1;
}

console.log(linearSearch(arr, 3)); // 2
console.log(linearSearch(arr, 5)); // 4
console.log(linearSearch(arr, 11)); // -1

이를 분할 정복 패턴이 적용된 이진 탐색으로 개선할 수 있다.

 

---

 

분할 정복 (Divide and Conquer)

• 배열이나 문자열 같은 큰 규모의 데이터셋을 처리한다.
• 그대로 해결할 수 없는 문제를 작은 문제(chunk)로 분할하여 문제를 해결하는 방법이다.
• 문제에 따라 시간 복잡도를 크게 줄일 수 있지만 항상 그렇지는 않다.

분할 정복 패턴의 처리 과정 (분할 - > 정복 - > 결합)

1. 분할(Divide) : 원래 문제를 작은 단위로 나눔
2. 정복(Conquer) : 문제의 단위가 해결할정도로 충분히 작아지면, 종료 조건으로 문제를 해결
3. 결합(Combine) : 작은 단위에서 해결된 문제들을 합쳐서 상위 문제를 해결

정렬된 정수 배열과, 값을 매개변수로 받는 search 함수가 있다. search 함수는 정수 배열에서 주어진 값의 인덱스를 리턴하는 함수이다. 만약 값이 주어진 배열에 존재하지 않는다면 -1을 리턴한다.

search([1, 2, 3, 4, 5, 6], 4) // 3
search([1, 2, 3, 4, 5, 6], 6) // 5
search([1, 2, 3, 4, 5, 6], 11) // -1

 

---

 

이분 탐색 / 이진 탐색 (Binary Search)

• 이진 탐색(이분 탐색) 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.
• 이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다.
• 변수 3개(start, end, mid)를 사용하여 탐색한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색의 과정이다.
  • 중간점이 찾는 원소가 아니라면 인덱스를 새롭게 정해주고, 탐색 범위는 반으로 줄어든다.
• 이진 탐색은 분할 정복 알고리즘의 한 예이다.
• 시간복잡도가 순차적 탐색보다 낮다.

 

프로세스

1. 처음 범위는 인덱스 0부터 끝까지이다. 이 때 중간 값을 mid로 한다.
2. 중간 값과 검색 값을 비교한다.
   • 중간 값이 검색 값과 같다면, 탐색 종료한다. (mid = key)
   • 중간 값보다 검색 값이 크다면, 중간값 기준 배열의 오른쪽 구간을 대상으로 탐색한다. (mid < key)
     •  left는 mid + 1로 하여 1을 다시 반복한다.
   • 중간 값보다 검색 값이 작다면, 중간값 기준 배열의 왼쪽 구간을 대상으로 탐색한다. (mid > key)
     • right는 mid - 1로 하여 1을 다시 반복한다.
3. 값을 찾거나 간격이 비어있을 때까지 반복한다.
   • 만약 left > right가 된다면 해당 배열에 찾는 원소가 없는 것이다.

 

이진 탐색의 분할정복 과정

• 분할 - mid를 기준으로 왼쪽, 오른쪽 배열으로 분할, value와 arr[mid]가 같다면 값을 반환 후 종료
• 정복 - value가 arr[mid]보다 작으면 mid를 기준으로 좌측 이진 탐색, 크면 우측 탐색
• 결합 - 탐색 결과가 직접 반환되어 결합은 필요하지않음

 

ex)

const binarySearch = (sortedArray, target) => {
  let left = 0;
  let right = sortedArray.length - 1;

  // 점점 좁혀지다가 left와 right의 순서가 어긋나게 되면 반복을 종료한다
  while (left <= right) {
    let mid = Math.floor((left + right) / 2); // 가운데 인덱스

    if (sortedArray[mid] === target)
      return mid;

    if (sortedArray[mid] < target) // 만약 37(target)이 sortedArray[mid]보다 크다면
      left = mid + 1; // left를 0에서 mid + 1으로 (mid를 기준으로 오른쪽 배열)
    else // 만약 37(target)이 sortedArray[mid]보다 작다면
      right = mid - 1; // right를 배열 끝에서에서 mid - 1으로 (mid를 기준으로 왼쪽 배열) 
  }

  return -1;
};

const arr = [1, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59];
console.log(binarySearch(arr, 37)); // 11

 

시간복잡도

평균	최선	최악
Θ(log n)	Ω(1)	O(log n)

• 시간 복잡도는 O(logN)이다. (여기서 log는 log₂이다.)
  
  • 단계마다 탐색 범위를 반으로(÷2) 나누는 것과 동일하므로 위 시간 복잡도를 가지게 된다.
    
  • 예를 들어 처음 데이터의 개수가 32개라면, 이론적으로 1단계를 거치면 약 16개의 데이터가 남고, 2단계에서 약 8개, 3단계에서 약 4개의 데이터만 남게 된다.
    
  • 즉, 이진 탐색(이분 탐색)은 탐색 범위를 절반씩 줄이고, O(logN)의 시간 복잡도를 보장한다.
• 순차적 탐색 : 최악의 경우, 배열의 끝까지 탐색해야한다 -> O(n)

 

장점

• 검색이 반복될 때마다 목푯값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다.
• 그렇다 보니 아무래도 선형 탐색의 시간 복잡도(O(N)) 보다는 이진 탐색의 시간 복잡도(O(logN))이 더 빠를 수밖에 없다.

단점

• 정렬된 데이터에만 이용할 수 있다.
  
• 삽입 / 삭제 연산 시에 데이터의 정렬 상태를 유지할 필요가 있다.
• 삽입 / 삭제가 빈번하면 적용하기 부적합하다.