이분 탐색 (Binary Search)

정렬된 배열에서 특정 값의 위치를 찾는 알고리즘

 

프로세스

• 배열의 중간 값을 확인
• 중간 값이 찾는 값이면 위치를 반환
• 중간 값보다 찾는 값이 작으면 왼쪽 부분에서 탐색을 계속
• 중간 값보다 찾는 값이 크면 오른쪽 부분에서 탐색을 계속
• 시간복잡도: O(log n)

function 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) left = mid + 1;
    else right = mid - 1;
  }
  return -1; // 요소를 찾지 못했을 때
}