정의

• 이분 탐색은 정렬된 데이터에서 특정 값을 빠르게 찾는 검색 알고리즘입니다.
• 탐색 범위를 절반으로 줄이며 진행하기 때문에 시간 복잡도가 **O(log N)**으로 매우 효율적입니다.

조건

1. 데이터가 정렬되어 있어야 한다.
2. 탐색 범위를 이분화하여 원하는 값을 찾는다.

동작 과정

1. 초기 설정:
   • 탐색 범위의 시작점 low와 끝점 high를 설정.
2. 중간값 계산:
   • mid = (low + high) / 2로 중간값 계산.
3. 조건 비교:
   • 목표값 == 중간값: 탐색 성공, 값을 반환.
   • 목표값 < 중간값: 중간값보다 작으므로 high = mid - 1.
   • 목표값 > 중간값: 중간값보다 크므로 low = mid + 1.
4. 반복:
   • low가 high보다 커질 때까지 위 과정을 반복.

장점

• 시간 복잡도가 **O(log N)**으로, 선형 탐색(O(N))보다 훨씬 빠르다.
• 데이터 크기가 클수록 효율성이 극대화된다.

단점

• 데이터가 정렬되어 있지 않으면 사용할 수 없다.
• 정렬이 선행되면 추가적인 시간 비용 발생 (O(N log N)).

시간 복잡도

• 최선의 경우: O(1) (중간값이 바로 목표값일 때)
• 최악의 경우: O(log N)