이진 탐색 (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);
console.log(`탐색 범위: index ${left} ~ ${right}, 중간값: ${arr[mid]}`);
if (arr[mid] === target) {
return mid; // 찾은 값의 인덱스 반환
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // 값을 찾지 못한 경우
}
const sortedArr = [1, 3, 5, 7, 9, 11, 13, 15];
const target = 11;
console.log("배열:", sortedArr);
console.log(`타겟 ${target}의 인덱스:`, binarySearch(sortedArr, target));