이진탐색

이진탐색이란?

이진 탐색(Binary Search)은 정렬된 배열이나 리스트에서 특정 값을 빠르게 찾기 위해 사용하는 효율적인 탐색 알고리즘입니다. 이진 탐색의 원리는 배열을 절반씩 나누어 검색 범위를 줄여 나가며 원하는 값을 찾는 것입니다.

1. 정렬된 배열 필요:
   이진 탐색은 배열이 정렬되어 있어야만 작동합니다. 정렬되지 않은 배열에서는 이진 탐색을 사용할 수 없습니다.

2. 중간값 선택:
   탐색 범위의 중간에 위치한 요소를 선택합니다.
   배열의 시작점 left와 끝점 right를 설정하고, 이 두 지점의 중간 인덱스를 계산하여 mid로 설정합니다.

3. 비교 후 범위 축소:
   중간값(mid)과 찾고자 하는 값(target)을 비교합니다.
   찾고자 하는 값이 중간값과 같다면: 탐색 종료. 값을 찾은 것입니다.
   찾고자 하는 값이 중간값보다 작다면: target은 배열의 왼쪽 부분에 있을 수 있으므로, right를 mid - 1로 설정하여 왼쪽 부분만 탐색합니다.
   찾고자 하는 값이 중간값보다 크다면: target은 배열의 오른쪽 부분에 있을 수 있으므로, left를 mid + 1로 설정하여 오른쪽 부분만 탐색합니다.

4. 반복:
   위 과정을 left가 right보다 작거나 같을 때까지 반복합니다. 찾고자 하는 값이 없으면 탐색을 종료합니다.

시간 복잡도:

시간 복잡도: O(log N)
매번 배열의 절반씩 줄여가며 탐색하므로 시간 복잡도가 로그 형태로 감소합니다.
공간 복잡도: O(1) (반복문을 사용하는 경우), O(log N) (재귀를 사용하는 경우 스택 공간 필요)

이진 탐색 반복 조건:

while (left < right)

left가 right보다 작을 때까지 탐색을 반복합니다. 탐색을 통해 left가 right와 같아지면 그 값이 구하려는 최소의 최대 패치 길이입니다.