이진 탐색(Binary Search)

이진 탐색은 정렬되어 있는 배열에서 탐색 범위를 절반씩 좁혀가며 원하는 값을 탐색하는 알고리즘이다. O(logN)의 시간복잡도를 가지며, 재귀 함수나 반복문으로 많이 작성한다.

 

재귀함수로 구현한 이진 탐색

      function binarySearch(arr, target, start, end) {
        if (start > end) {
          return -1;
        }

        let mid = parseInt((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);
        }
      }

 

while문으로 구현한 이진 탐색

      function binarySearch(arr, target, start, end) {
        while (start <= end) {
          let mid = parseInt((start + end) / 2);
          if (arr[mid] == target) {
            return mid;
          } else if (arr[mid] > target) end = mid - 1;
          else {
            start = mid + 1;
          }
        }
        return -1;
      }