[알고리즘] 이진 탐색

이진 탐색(Binary Search)은 정렬된 데이터에서 원하는 값을 효율적으로 찾는 알고리즘
순차적으로 모든 데이터를 확인하는 선형 탐색과는 달리, 이진 탐색은 탐색 범위를 절반씩 줄여나가면서 원하는 값을 찾는다. 따라서 데이터의 크기가 커질수록 선형 탐색에 비해 훨씬 빠른 속도를 보인다.

이진 탐색의 작동 순서:

1. 정렬: 이진 탐색을 적용하기 위해서는 데이터가 반드시 오름차순 또는 내림차순으로 정렬되어 있어야 한다.
2. 중간값 찾기: 배열의 중간에 있는 데이터의 인덱스를 찾아서 저장한다.
3. 비교: 찾고자 하는 값과 중간값을 비교한다.
   • 찾는 값과 중간값이 같다면, 탐색 성공.
   • 찾는 값이 중간값보다 작다면, 중간값을 기준 왼쪽 배열의 중간값으로 다시 탐색
   • 찾는 값이 중간값보다 크다면, 중간값을 기준 오른쪽 배열의 중간값으로 다시 탐색
4. 범위 축소: 비교 결과에 따라 탐색 범위를 절반으로 줄어든다
5. 반복: 찾는 값을 찾을 때까지 또는 탐색 범위가 더 이상 없을 때까지 반복

예시:

오름차순으로 정렬된 배열 [2, 5, 7, 8, 11, 12]에서 값 11을 찾는 과정을 예로 들어보면

1. 초기 범위: 배열 전체 array[6] = { 2, 5, 7, 8, 11, 12 }
2. 1단계:
   • 중간 인덱스: array[(length - 1) / 2]
   • 중간값: array[2] = 7
   • 찾는 값(11) > 중간값(7) 이므로, 탐색 범위를 오른쪽 절반 (index 3 ~ 5)으로 좁힌다.
3. 2단계:
   • 새로운 범위: 인덱스 array[3~5]
   • 중간 인덱스: array[(3+5) / 2]
   • 중간값: array[4] = 11
   • 찾는 값(11) == 중간값(11) 이므로, 탐색 성공. 인덱스 4를 반환

시간 복잡도:

이진 탐색은 매번 탐색 범위를 절반으로 줄이기 때문에 시간 복잡도는 O(log n)
이는 데이터의 양이 아무리 많아져도 탐색 횟수가 로그 함수에 비례하여 매우 빠르게 증가한다
따라서 대규모 데이터셋에서 원하는 값을 검색할 때 매우 효율적인 알고리즘이다.

주의사항:

• 이진 탐색은 반드시 정렬된 데이터에서만 사용할 수 있다.
• 정렬되지 않은 데이터에 이진 탐색을 적용하면 정확한 결과를 보장할 수 없다.