이진 탐색(Binary Search)은 정렬된 배열에서 특정한 값을 찾는 효율적인 알고리즘입니다. 이진 탐색의 기본 아이디어는 배열을 반으로 나누어 원하는 값이 있는 부분을 반복적으로 좁혀 나가는 것입니다. 이 글에서는 이진 탐색 알고리즘에 대한 자세한 설명과 함께 문제를 풀어보겠습니다.
문제 설명
다음은 이진 탐색을 활용하여 해결할 수 있는 문제입니다:
문제: 이진 탐색을 사용하여 배열에서 특정 값 찾기
정렬된 배열 nums와 정수 target가 주어질 때, target의 인덱스를 반환하세요. target이 배열에 존재하지 않으면 -1을 반환합니다. 함수는 nums가 오름차순으로 정렬되어 있다고 가정합니다.
예시
입력: nums = [-1,0,3,5,9,12], target = 9 출력: 4 입력: nums = [-1,0,3,5,9,12], target = 2 출력: -1
이진 탐색 알고리즘의 원리
이진 탐색 알고리즘은 다음과 같은 절차로 검색을 진행합니다:
- 배열의 중간 인덱스(middle)를 계산합니다.
- 중간값이 찾고자 하는 값(target)과 비교합니다:
- 중간값이 target과 같으면 중간 인덱스를 반환합니다.
- 중간값이 target보다 작으면 오른쪽 절반을 검색합니다. (중간 인덱스 + 1 부터 끝까지)
- 중간값이 target보다 크면 왼쪽 절반을 검색합니다. (시작부터 중간 인덱스 – 1 까지)
- 정확한 값을 찾을 때까지 이 과정을 반복합니다.
이진 탐색의 시간 복잡도는 O(log n)으로, 대량의 데이터에서 빠르게 검색할 수 있는 장점이 있습니다.
문제 해결 과정
이제 위의 문제를 해결하기 위해 코드를 작성해 보겠습니다. 첫 번째로 배열과 target을 받아들이는 함수를 정의합니다.
function binarySearch(nums, target) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2); // 중간 인덱스 계산
if (nums[mid] === target) {
return mid; // 찾은 경우 중간 인덱스 반환
} else if (nums[mid] < target) {
left = mid + 1; // 오른쪽 절반으로 이동
} else {
right = mid - 1; // 왼쪽 절반으로 이동
}
}
return -1; // 값이 없는 경우 -1 반환
}
코드 설명
위 코드에서 binarySearch 함수는 nums 배열과 target 값을 인자로 받아서 이진 탐색을 수행합니다.
left와right변수를 사용하여 검색 범위를 설정합니다. 초기 값은 각각 배열의 시작과 끝 인덱스입니다.- while 루프를 사용하여
left가right보다 작거나 같은 동안 반복합니다. - 각 반복마다 중간 인덱스를 계산하고, 중간값을
target과 비교합니다. - 조건에 따라 검색 범위를 조정하고, 최종적으로 값을 찾지 못한 경우 -1을 반환합니다.
예제 실행
아래는 이진 탐색 함수의 예제 실행입니다:
const nums = [-1,0,3,5,9,12];
console.log(binarySearch(nums, 9)); // 출력: 4
console.log(binarySearch(nums, 2)); // 출력: -1
결과 분석
위의 예제를 통해 함수가 올바른 인덱스를 출력하는 것을 확인할 수 있습니다. binarySearch(nums, 9)는 4를 반환하고, binarySearch(nums, 2)는 -1을 반환합니다.
결론
이진 탐색은 매우 효율적인 탐색 알고리즘으로, 정렬된 데이터에서 원하는 값을 빠르게 찾을 수 있습니다. 이번 강좌를 통해 이진 탐색의 원리와 구현 방법을 이해하셨길 바랍니다. 실제 코딩 테스트에서도 자주 등장하는 알고리즘이므로, 반드시 숙지하고 연습하는 것이 중요합니다.