Colin's Blog
[javascript] 반복문을 이용한 이진 탐색 알고리즘 구현하기
  1. 이진 탐색 알고리즘 개요
  2. 반복문을 이용한 이진 탐색 알고리즘 구현
  3. 예시 코드
  4. 참고 자료

이진 탐색 알고리즘 개요

이진 탐색 알고리즘은 정렬된 배열에서 특정한 값을 찾는 알고리즘이다. 이 알고리즘은 배열의 중간값을 기준으로 값을 비교하고, 찾고자 하는 값이 중간값보다 작으면 왼쪽 절반을, 크면 오른쪽 절반을 탐색하는 방식으로 동작한다. 이렇게 찾고자 하는 값을 찾을 때까지 이 과정을 반복한다.

반복문을 이용한 이진 탐색 알고리즘 구현

이진 탐색 알고리즘을 구현할 때 반복문을 사용하여 구현할 수 있다. 반복문을 이용한 구현은 별도의 스택을 사용하지 않기 때문에 메모리를 덜 사용하고, 일반적으로 재귀를 사용한 구현보다 더 빠르게 동작한다.

다음은 반복문을 이용한 이진 탐색 알고리즘의 구현 예시이다.

예시 코드

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1;
}

참고 자료

© 2018 Colin. All rights reserved.