[JavaScript] 이진 탐색(Binary Search) 알고리즘

"이진 탐색 알고리즘의 이해와 적용"

---

1. 이진탐색이란?

데이터가 정렬되어 있는 배열에서 특정한 값을 찾는 알고리즘.
ㄴ _본 게시글의 예시의 경우 오름차순으로 되어 있는 데이터를 사용
배열의 있는 임의의 중간 값을 선택하여 찾고자 하는 값 X 와 비교한다.
X 가 중간 값보다 작으면 좌측 데이터를 대상으로,
X 가 중간 값보다 크면 우측 데이터를 대상으로 다시 탐색한다.
X 값을 찾을 때까지 동일한 방법을 반복한다.
_(up-down 숫자맞추기 게임과 유사)

Database Index 적용의 장단점

장점 - Full Table Scan에 비해 데이터 검색 속도 및 성능이 향상된다.

단점 - 탐색을 위한 정렬된 테이블이 추가되기 때문에 메모리를 사용한다.

    - DB가 수정될 때마다 인덱스의 업데이트가 필요하다.

---

2. 이진탐색의 예시

오름차순으로 정렬된 배열이 있다.

{ 10, 15, 33, 48, 59, 66, 80}

이진 탐색을 이용하여 33를 찾아본다.

- 첫 번째 시도

우선 가운데에 위치한 임의의 값 48을 선택.
선택한 값 48과 찾고자 하는 값 33를 비교한다.
33 < 48 이므로 33은 48의 좌측에 존재한다는 것을 알 수 있다.

- 두 번째 시도

48을 기준으로 좌측에 있는 배열 값들을 대상으로 다시 탐색을 진행한다.

{ 10, 15, 33 }

마찬가지로 가운데의 임의의 값 15을 선택한다.
15 < 33 이번에는 15가 33보다 작으므로 15 우측에 위치하는 것을 알 수 있다.

- 세 번째 시도

15의 우측을 기준으로 배열을 다시 설정해보면

{ 33 }
배열에 값이 하나만 남게 되고 값을 확인해보면,
33 == 43 원하는 값을 찾았다.

- 종료조건

1. 탐색의 종료 조건은 원하는 값을 찾으면 종료.
2. 탐색하고자 하는 값이 배열에서 없을 경우 값이 없는 것으로 판단하여 종료.

---

3. JavaScript를 통한 소스코드 구현

이진 탐색은 정렬되어 있는 배열이 필요로 하며 각 left, right, mid의 변수가 필요하다.

left은 왼쪽의 끝 인덱스를 뜻하며 right는 오른쪽의 끝 인덱스를 뜻하고 left와 right의 사이는 탐색범위가 된다.

변수명은 (low, high) 또는 (start, end)로 바꿀 수도 있다.

mid는 left와 right 범위의 중간점을 뜻하며 탐색하는 범위에서의 중간에 위치한다.

이때 중간점은 (left + right) / 2 란 공식으로 구할 수 있다.

이진 탐색의 시간 복잡도는 O(logN)이며 단순히 매번 절반의 탐색할 데이터를 제외시킨다 생각할 수 있다.

탐색범위의 중간 인덱스를 지정하고 찾고자 하는 값(target)과 현재 중간 값을 비교한다.

이때 target 값과 중간 값의 비교 값에 따른 조건을 걸어준다.

• 중간 값보다 target 값이 크다면 중간 값보다 작은 수는 더 이상 범위에 해당하지 않기에 left의 값은 mid + 1이 된다.
• 중간 값보다 target 값이 작다면 중간 값보다 큰 수는 더 이상 범위에 해당하지 않기에 right의 값은 mid - 1이 된다.

이를 반복하며 만약에 target 값과 중간 값이 일치하면 해당 mid의 위치에 찾는 값이 존재하므로 해당 값을 반환해주고, left와 right의 값이 mid의 값과 같음에도 중간 값이 일치하지 않으면 배열에 찾는 값이 존재하지 않으므로 -1을 반환한다.

const binarySearch = (list, target, left, right) => {
  let mid = 0;

  while (left <= right) {
    // 가운데 인덱스
    mid = Math.floor((left + right) / 2);

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

    // 대소 비교로 범위 지정
    if (list[mid] > target) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }

  return -1;
}

const sample = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

sample.sort((a, b) => a - b);

// ( 찾을 배열, 탐색할 값, 시작점, 끝점 )
const result = binarySearch(sample, 7, 0, sample.length - 1);

console.log(result);