[AL] 이진 탐색 - JavaScript

탐색 관련 문제를 처음 접하게 되면 for문을 이용하여 모든 값을 다 확인하여 원하는 값을 찾아내는 정말 간단하지만 효율성은 0인 방법을 사용하게 된다.

하지만 그 이후로 효율성의 중요성을 느끼고 찾게 되는 탐색 알고리즘이 바로 이진 탐색 (Binary Search) 알고리즘이다.

이진 탐색 (Binary Search)

주어진 데이터가 정렬 되어 있을 때, 특정 값을 찾아내는 알고리즘을 의미한다.

이진 탐색에서 가장 중요한 조건은 바로 정렬이 되어 있어야 한다는 것이다. 정렬이 되어있지 않거나, 정렬을 할 수 없는 데이터의 경우에는 이진 탐색을 이용할 수 없다는 점!

정렬된 데이터가 담긴 배열에서 원하는 값 X를 찾고자 할 때 배열의 중간 값 M을 선택하여 X와 비교한다.

• 만약 X가 M보다 작으면 M을 기준으로 좌측 (배열의 가장 작은값 ~ M)을 대상으로,
• 만약 X가 M보다 크면 M을 기준으로 우측 (M+1 ~ 배열의 가장 큰 값)을 대상으로 다시 탐색한다.

이 과정을 X 를 찾을 때 까지 반복한다!

구현 코드

반복문 사용

// arr: 정렬된 배열, target: 찾고자 하는 값
const 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){
      right = mid-1;
    }else{
      left = mid+1;
    }
  }
  return -1;
}

재귀 사용

// arr: 정렬된 배열, target: 찾고자 하는 값
const binarySearch = (arr, target, left, right) => {
  if(left > right) return -1;
  
  let mid = Math.floor((left+right)/2);
  if(arr[mid] === target){
    return mid;
  }else if(arr[mid] > target){
    return binarySearch(arr, target, left, mid-1);
  }else{
    return binarySearch(arr, target, mid+1, right);
  }
}