이진 탐색
이진 탐색(binary search)은 정렬된 배열에서 원하는 값을 효율적으로 찾는 알고리즘입니다.
이진 탐색은 배열의 중간 값을 사용하여 원하는 값이 왼쪽 반쪽에 있는지 오른쪽 반쪽에 있는지를 결정한 다음, 그 범위를 반으로 줄여나가며 원하는 값을 찾습니다.
이 과정을 반복하면 원하는 값이 있는지 여부와 해당 값의 인덱스를 찾을 수 있습니다.
이진 탐색의 시간 복잡도
이진 탐색의 시간 복잡도는 O(log n)입니다.
이는 정렬된 배열에서 원하는 값을 매우 빠르게 찾을 수 있다는 것을 의미합니다.
하지만, 정렬되지 않은 배열의 경우 이진 탐색을 사용할 수 없어 정렬 시간도 포함되어야 합니다.
이진 탐색의 탐색 방법
아래 그림은 이진 탐색을 설명하기 위한 그림입니다.
문제는 숫자 4가 현재 몇 번째에 위치하는 지를 구하는 문제라고 합시다.
1.
시작점과 끝점을 설정합니다.
•
시작 인덱스: 0
•
끝 인덱스: 9
2.
다음으로 중간점을 선택합니다.
•
(시작 인덱스 + 끝 인덱스) / 2
3.
현재 중간점이 숫자 4보다 크거나 같은지 작은지 확인하고, 크거나 같다면 오른쪽, 작다면 왼쪽 지점을 탐색합니다.
•
더 작으므로 왼쪽 지점을 탐색합니다.
•
시작 인덱스: 0
•
끝 인덱스: 중간점
4.
이러한 과정을 시작 인덱스가 끝 인덱스를 넘어설 때까지 반복합니다.
5.
시작 인덱스가 끝 인덱스를 넘어섰다면, 현재 끝 인덱스가 정답의 위치입니다.
이진 탐색의 구현
while start <= end:
mid = (start + end) / 2
if data[mid] <= target:
start = mid + 1
else:
end = mid
// end가 정답 인덱스 이다.
// 정답이 없을 경우 한 번더 감사가 필요.
C#
복사
