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

✏️ 순차 탐색 vs 이진 탐색

• 순차 탐색: 리스트 안에 있는 특정 데이터를 찾기 위해 앞에서부터 하나씩 확인하는 방법입니다. 시간 복잡도 0(N)
• 이진 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가면서 데이터를 탐색하는 방법입니다. 시간 복잡도 0(logN)

✏️ 이진 탐색 동작 방식

이진 탐색을 수행할 때는 시작점(left)과 끝점(right)을 기준으로 탐색 범위를 명시해 줍니다.
시작점과 끝점의 중간 지점인 mid 값을 확인 후 찾아야 하는 데이터 값과 비교해 줍니다.
mid 값이 더 작다면 left를 mid의 인덱스 번호 + 1 값으로 변경해서 범위를 좁혀주고, 마찬가지로 left와 right의 중간 값을 구한 후 비교해주는 방식으로 범위를 점점 좁혀가며 데이터를 찾을 수 있습니다.

이진 탐색은 주로 매우 넓은 탐색 범위에서 최적의 값을 찾아야 하는 경우나 데이터를 정렬한 뒤에 다수의 쿼리를 날려야 하는 경우에 효과적으로 사용됩니다.

✏️ 이진 탐색 코드 예시

재귀 함수

// 숫자 7이 몇번째 있는지 찾는 코드
function solution() {
  let nums = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];
  let k = 7;
  function binarySearch(arr, target, start, end) {
    // 값이 없는 경우
    if (start > end) return -1;
    let mid = Math.floor((start + end) / 2);
    // 찾은 경우 중간 인덱스 반환
    if (arr[mid] === target) return mid;
    // 중간점의 값보다 찾는 값이 작은 경우 끝점을 중간 인덱스로 변경
    else if (arr[mid] > target)
      return binarySearch(arr, target, start, mid - 1);
    // 찾는 값이 중간 값보다 큰경우 시작점을 중간 인덱스로 변경
    else return binarySearch(arr, target, mid + 1, end);
  }

  let answer = binarySearch(nums, k, 0, nums.length - 1);
  return answer + 1;
}

console.log(solution());

반복문

// 숫자 7이 몇번째 있는지 찾는 코드
function solution() {
  let nums = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];
  let k = 7;
  function binarySearch(arr, target, start, end) {
    while (start <= end) {
      let mid = Math.floor((start + end) / 2);
      if (arr[mid] === target) return mid;
      else if (arr[mid] > target) end = mid - 1;
      else start = mid + 1;
    }
    // 값이 없는 경우
    return -1;
  }
  let answer = binarySearch(nums, k, 0, nums.length - 1);
  return answer + 1;
}

console.log(solution());