[알고리즘][JS] 이진 탐색(Binary Search)

• 이진 탐색(Binary Search) 개념

배열 및 리스트를 반으로 나누어 탐색 범위를 줄여나가는 식으로 동작하는 알고리즘

대용량의 데이터 처리에 효과적

이진탐색을 구현하기 위한 배열 및 리스트는 반드시 정렬 되어 있어야 함.

 

이진탐색 구현법

정렬된 배열, start 인덱스, end 인덱스

배열을 반으로 나누었을때 경우의 수 3가지

• 중간 값이 찾고자하는 값과 같을때 - 검색성공을 return
• 중간 값이 찾고자하는 값보다 작을때 - 반으로 나눈 왼쪽 요소를 이진탐색
• 중간 값이 찾고자하는 값보다 클때 - 반으로 나눈 오른쪽 요소를 이진탐색

이진탐색 설명

복잡도

O(log n)

이진 검색 알고리즘 풀이

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

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);

    // 중간 요소와 타겟을 비교
    if (states[mid] === target) {
      return mid; // 찾았을 때의 인덱스 반환
    }

    // 중간 요소가 타겟보다 작으면 오른쪽 반 탐색
    if (states[mid] < target) {
      left = mid + 1;
    }
    // 중간 요소가 타겟보다 크면 왼쪽 반 탐색
    else {
      right = mid - 1;
    }
  }

  return -1; // 찾지 못한 경우 -1 반환
}