이진 탐색의 기본 원리 및 구현 세부사항
이진 탐색은 정렬된 배열에서 O(log n) 시간 복잡도로 특정 항목의 위치를 찾는 효율적인 알고리즘입니다. 중간 요소를 기준으로 탐색 범위를 절반씩 좁혀나가는 방식으로 작동합니다. 구현 시 mid 값 계산은 low + (high - low) / 2를 사용하여 정수 오버플로우를 방지하는 것이 중요하며, 이는 기술 면접에서 지원자의 전문성을 보여줄 수 있습니다.
이진 탐색의 주요 변형 알고리즘
기본 이진 탐색 외에, 실제 문제 해결을 위해 다음과 같은 네 가지 변형이 중요하게 다루어집니다. 각 변형은 result 변수를 활용하여 조건을 만족하는 최적의 인덱스를 저장하고, 탐색 범위를 조정합니다.
-
중복 시 가장 작은 인덱스: 항목 발견 시
result업데이트 후high = mid - 1로 탐색을 계속하여 더 작은 인덱스를 찾습니다. -
중복 시 가장 큰 인덱스: 항목 발견 시
result업데이트 후low = mid + 1로 탐색을 계속하여 더 큰 인덱스를 찾습니다. -
주어진 값보다 작은 가장 큰 값:
items[mid] < item일 경우result업데이트 후low = mid + 1로 이동하여 더 큰 값을 탐색합니다. -
주어진 값보다 큰 가장 작은 값:
items[mid] > item일 경우result업데이트 후high = mid - 1로 이동하여 더 작은 값을 탐색합니다.
이러한 변형들은 기본 알고리즘에 대한 깊은 이해를 바탕으로 다양한 문제에 적용될 수 있습니다.