[알고리즘 공부] 이진탐색 (이분탐색)

---

참고

이진탐색 (이분탐색)

---

이진 탐색 알고리즘(Binary Search Algorithm)은 이미 정렬되어 있는 배열에서 탐색 범위를 두 부분 리스트로 나눠 절반씩 좁혀가 필요한 부분에서만 탐색하도록 제한하여 원하는 값을 찾는 알고리즘입니다.

예를 들어 1부터 10까지의 배열에서 3을 찾는다면 찾는 배열의 중간인 5를 기준으로 대소를 비교하고 3은 5보다 작기 때문에 두 부분 나눈 리스트에서 5 이상은 탐색범위에서 제외시키고 5 이하의 부분에서 다시 탐색하게 되는 방식입니다.

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

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

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

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

이진 탐색의 시간 복잡도는 O(logN)이며 단순히 매번 절반의 탐색할 데이터를 제외시킨다 생각하면 될 것 같습니다.

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

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

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

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

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

JS 코드

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);