js로 이분탐색 구현

1. 이분탐색이란 ? 

이분 탐색(Binary Search)은 정렬된 배열에서 값을 찾는 효율적인 탐색 알고리즘
배열을 절반으로 나누면서 목표 값을 찾기 때문에 시간 복잡도가 O(log n)

: 조건은 배열이 반드시 정렬되어 있어야 한다는 점 !!

 

2. 이분 탐색 과정 

1. 배열의 중간 값을 확인한다.
2. 중간 값이 찾으려는 값보다 크면, 왼쪽 절반을 탐색한다.
3. 중간 값이 찾으려는 값보다 작으면, 오른쪽 절반을 탐색한다.
4. 값을 찾을 때까지 이 과정을 반복한다.

 

3.이분 탐색의 JavaScript 구현

 

JavaScript로 이분 탐색을 구현하는 방법은 두 가지가 있다. 
재귀 함수와 반복문을 사용하는 방식 

 

(1) 재귀를 이용한 이분탐색 구현 

function binarySearch(arr, target, start = 0, end = arr.length - 1) {
  if (start > end) {
    return -1; // 찾는 값이 없을 경우
  }

  const 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); // 오른쪽 절반을 탐색
  }
}

 

(2) 반복문을 이용한 이분탐색 구현 

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

  while (start <= end) {
    const 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; // 찾는 값이 없을 경우
}