[Algorithm]Sort-Binary Search

Binary Search(이진 검색)은 정렬된 목록에서 요소를 찾기 위한 효율적인 알고리즘입니다. 이 알고리즘은 목록을 반으로 나누고 검색 중인 요소가 목록의 하위 또는 상위 절반에 있는지 확인하는 방식으로 작동합니다. 이를 반복함으로써, 알고리즘은 요소가 발견되거나 부재로 결정될 때까지 검색 범위를 빠르게 좁힐 수 있다.

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

  while (left <= right) {
    const 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;
}

함수는 검색할 정렬된 배열과 대상 값의 두 가지 인수를 사용합니다. 왼쪽 및 오른쪽 경계를 배열의 첫 번째 인덱스와 마지막 인덱스로 각각 설정하는 것으로 시작합니다. 그런 다음 함수는 왼쪽 경계가 오른쪽 경계보다 작거나 같은 동안 계속되는 while 루프에 들어갑니다.

루프 내부에서 함수는 왼쪽 및 오른쪽 경계를 추가하고 결과를 2로 나누어 현재 검색 범위의 중간 인덱스를 계산합니다(산술을 사용하여 반올림). 중간 인덱스의 요소가 목표값과 같으면 함수는 중간 인덱스를 반환합니다.

중간 요소가 대상보다 작으면 함수는 왼쪽 경계를 중간 인덱스 + 1로 업데이트하여 검색 범위의 하위 절반을 효과적으로 제거합니다. 중간 요소가 목표값보다 크면 함수는 오른쪽 경계를 중간 인덱스에서 1을 뺀 값으로 업데이트하여 검색 범위의 위쪽 절반을 효과적으로 제거합니다.

함수가 대상을 찾지 않고 while 루프를 완료하면 -1을 반환하여 대상이 배열에 없음을 나타냅니다.

const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
const target = 5;

console.log(binarySearch(arr, target)); // Output: 4

이 예에서 배열은 [1, 2, 3, 4, 5, 6, 7, 8, 9]이고 대상 값은 5입니다. 함수는 목표값의 인덱스(4)를 반환합니다(배열은 0-인덱스임을 기억하십시오).

이진 검색은 정렬된 목록에서 요소를 빠르게 찾을 수 있는 강력한 알고리즘입니다. 검색 범위를 지속적으로 절반으로 나누면 각 반복에서 나머지 요소의 절반을 효율적으로 제거할 수 있습니다.