[Algorithm] 이진 탐색 (Binary Search)

이진 탐색 (Binary Search)

이진 탐색이란 정렬되어있는 데이터가 담긴 배열에서 특정한 값을 효과적으로 찾아낼 수 있는 알고리즘이다. 배열 중간에 있는 값을 기준으로 찾고자 하는 값과 비교한뒤 해당 값이 중간 값보다 작으면 중간 값을 기준으로 좌측의 원소들을 대상으로, 중간 값보다 크면 우측의 원소로, 즉 절반을 자른 뒤 새 범위 내에서 다시 탐색한다. 이런식으로 해당 값을 찾을 때까지 계속 중간 값을 비교하며 탐색해 나간다.

예시

정렬된 숫자로 구성된 배열 [1, 3, 4, 7, 9, 11, 13]에서 4를 탐색할 시, 우선 해당 배열의 전체 길이의 중간 값인 7을 선택한뒤 탐색값인 4와 비교한다. 비교 시 7은 4보다 크므로 7을 기준으로 왼쪽 요소들로 탐색을 이어가는데 이미 7은 검색했으므로, [1,3,4]에서 다시 중간값인 3을 탐색값과 비교한다. 3은 4보다 작으므로, 오른쪽 요소로 탐색을 전환하는데, 이때 7부터는 검사를 마쳤으므로, 4가 탐색되게 된다.

구현

반복문

const binarySearch = function (arr, target) {
  let answer = -1;
  let start = 0;
  let end = arr.length;
  while (start <= end) {
    console.log(start);
    let mid = Math.floor((start + end) / 2);

    if (arr[mid] === target) {
      answer = mid;
      return answer;
    }
    if (arr[mid] > target) {
      end = mid - 1;
    } else {
      start = mid + 1;
    }
  }
  return answer;
};

재귀

const binarySearch = function (arr, target) {
  let answer = -1;
  const recur = (start, end) => {
    let mid = Math.floor((start + end) / 2);
    arr[mid] === target ? (answer = mid) : arr[mid];
    if (start >= end) {
      return;
    }
    arr[mid] > target ? recur(start, mid - 1) : recur(mid + 1, end);
  };

  recur(0, arr.length);
  return answer;
};