이진 검색 알고리즘은 정렬된 배열에서 특정 값을 찾는 효율적인 방법입니다. 이 접근 방식은 배열을 더 작은 부분으로 나누고 검색 범위의 중간 위치에 있는 값과 대상 값을 지속적으로 비교합니다. 값이 일치하면 원하는 값을 찾습니다. 그렇지 않으면 알고리즘은 계속해서 검색 범위를 좁히고 값을 찾거나 검사할 요소가 더 이상 남지 않을 때까지 프로세스를 반복합니다.
단계:
- 검색 범위 초기화: 배열의 첫 번째 위치에서
left마지막 위치까지 검색 범위를 선택하여 시작합니다.right - 중간점 찾기: 및 올바른 위치를 평균하여 중간점을 계산합니다
left. 이것은 검색 범위의 중간 지점입니다. - 값 비교: 중간 지점의 값과 목표 값을 비교합니다.
- 비교 결과 처리: 중간 지점의 값이 목표 값과 일치하면 이 위치를 반환합니다. 중간 지점의 값이 목표 값보다 작으면 왼쪽 위치를 중간 + 1로 업데이트하여 오른쪽 절반을 검색합니다. 중간 지점의 값이 목표 값보다 크면 오른쪽 위치를 중간- 1로 업데이트하여 왼쪽 절반을 검색합니다.
- 반복: 값을 찾거나 더 이상 확인할 요소가 없을 때까지 2~4단계를 반복합니다
left > right.
장점과 단점
이점:
- 효율적인 성능: 알고리즘의 시간 복잡도는 O(log n)이므로 대용량 데이터 세트를 처리하는 데 매우 효율적입니다.
- 대규모 데이터 세트에 효과적: 이진 검색은 대규모 데이터 세트에 대해 빠르게 검사할 요소 수를 줄이는 데 효과적입니다.
단점:
- 정렬된 배열에만 적용 가능: 알고리즘은 정렬된 배열에서만 작동합니다.
- 가변 단계 수: 값을 찾는 데 필요한 단계 수는 배열에서의 위치에 따라 다르며 끝 근처의 값에 대해 많은 단계를 거칠 수 있습니다.
예: PHP의 정렬된 배열에서 값 12를 찾기 위한 이진 검색
function binarySearch($arr, $target) {
$left = 0;
$right = count($arr)- 1;
while($left <= $right) {
$mid = floor(($left + $right) / 2);
if($arr[$mid] == $target) {
return $mid; // Return the position of the value
} elseif($arr[$mid] < $target) {
$left = $mid + 1;
} else {
$right = $mid- 1;
}
}
return -1; // Value not found
}
$array = [2, 5, 8, 12, 15, 20, 30];
$targetValue = 12;
$result = binarySearch($array, $targetValue);
if($result != -1) {
echo "Value $targetValue found at position $result.";
} else {
echo "Value $targetValue not found in the array.";
}
예의 설명
- 배열의 첫 번째 위치에서
left = 0마지막 위치까지의 초기 검색 범위로 시작합니다.right = 6 - 왼쪽과 오른쪽 위치를 평균하여 중간 지점(mid)을 계산합니다.
mid = 3. mid의 값은 12입니다. -
mid(12)의 값을 대상 값(12)과 비교하고 일치하는 항목을 찾으므로 위치 3을 반환합니다. - 알고리즘이 종료되고 "위치 3에서 찾은 값 12"라는 결과를 출력합니다.