[알고리즘] 이진 탐색(Binary Search)

📌  이진 탐색이란?

이진 탐색(Binary Search)은 정렬된 데이터에서 원하는 값을 효율적으로 탐색하는 알고리즘! 🎯

기능	특징	시간 복잡도
타깃 데이터 탐색	중앙값 비교를 통한 대상 축소 방식	O(logN)

 

 

🔍 이진 탐색의 주요 특징

• 빠른 탐색
  • 이진 탐색은 정렬된 데이터에서 탐색을 수행하므로 **O(log N)**의 시간 복잡도를 가진다.
  • 데이터 크기가 커질수록 선형 탐색보다 훨씬 효율적이다.
• 정렬 필수
  • 이진 탐색을 사용하기 위해선 데이터가 반드시 정렬되어 있어야 한다.
  • 정렬이 되어 있지 않다면, 먼저 정렬한 후 탐색해야 한다.

 

 

🔧 이진 탐색의 활용과 문제 유형

• 활용 사례
  • 🔢 숫자 데이터 탐색
  • 📚 사전처럼 정렬된 텍스트 탐색
  • 🛒 가격 또는 범위를 기준으로 정렬된 상품 탐색
• 문제 유형
  • ✅ 특정 값의 존재 여부 확인
  • ✅ 특정 조건을 만족하는 값의 최대/최소 찾기
  • ✅ Lower Bound / Upper Bound 문제

 

 

🚫 이진 탐색 사용 시 주의할 점

• 정렬 여부 확인
  • 탐색 전 데이터가 정렬되어 있는지 반드시 확인해야 해요!
  • 정렬이 안 되어 있다면 오름차순 정렬을 먼저 수행해야 해요.
• 무한 루프 방지
  • 탐색 범위를 좁히지 못하면 무한 루프에 빠질 수 있어요.
  • 매번 left, right 값을 적절히 업데이트해야 해요.
• 정확한 종료 조건 설정
  • while (left <= right)와 같은 종료 조건이 중요해요.
  • 종료 조건이 없으면 탐색이 끝나지 않아요!

 

 

🥐 이진 탐색 과정

⭐️ 오름차순 정렬 기준

1️⃣ 중앙값 선택

• 현재 탐색 범위의 중앙값을 선택
• 중앙값 =  (left + right) / 2

2️⃣ 타깃과 비교

• 중앙값이 타깃 값보다 큰지 작은지 비교
  • 중앙값 > 타깃 값: 왼쪽 범위를 탐색.
  • 중앙값 < 타깃 값: 오른쪽 범위를 탐색.

3️⃣ 범위 업데이트

• 왼쪽 또는 오른쪽 범위를 갱신:
  • 왼쪽 탐색: right = mid - 1.
  • 오른쪽 탐색: left = mid + 1

4️⃣ 탐색 종료

• 중앙값 == 타깃 값: 탐색 성공! 🎉
• left > right: 탐색 실패.

 

⭐️ 내림차순 정렬 기준

1️⃣ 중앙값 선택

• 현재 탐색 범위의 중앙값을 선택
• 중앙값 =  (left + right) / 2

2️⃣ 타깃과 비교

• 중앙값이 타깃 값보다 큰지 작은지 비교
  • 중앙값 < 타깃 값: 왼쪽 범위를 탐색.
  • 중앙값 > 타깃 값: 오른쪽 범위를 탐색.

3️⃣ 범위 업데이트

• 왼쪽 또는 오른쪽 범위를 갱신:
  • 왼쪽 탐색: right = mid - 1
  • 오른쪽 탐색: left = mid + 1

4️⃣ 탐색 종료

• 중앙값 == 타깃 값: 탐색 성공! 🎉
• left > right: 탐색 실패.

🔍 정리

• 오름차순 정렬: 타깃 값이 중앙값보다 작으면 왼쪽, 크면 오른쪽!
• 내림차순 정렬: 타깃 값이 중앙값보다 크면 왼쪽, 작으면 오른쪽!

 

 

💡 이진 탐색 동작 방식 예제

✅ 데이터셋
3, 7, 13, 15, 23, 35, 38, 41, 46, 49, 55, 67, 68, 72, 77, 86

 

1️⃣ 초기 설정

• 탐색 범위: left = 0, right = 15 (배열 인덱스 기준).
• 중앙값 계산: mid = (left + right) / 2 = (0 + 15) / 2 = 7.
• 중앙값 데이터: 41.

🔎 비교:

• 41 < 55.
• 결론: 55는 41보다 크므로, 오른쪽 범위를 탐색.
• 새로운 탐색 범위: left = 8, right = 15.

2️⃣ 두 번째 탐색

• 탐색 범위: left = 8, right = 15.
• 중앙값 계산: mid = (8 + 15) / 2 = 11.
• 중앙값 데이터: 67.

🔎 비교:

• 67 > 55.
• 결론: 55는 67보다 작으므로, 왼쪽 범위를 탐색.
• 새로운 탐색 범위: left = 8, right = 10.

3️⃣ 세 번째 탐색

• 탐색 범위: left = 8, right = 10.
• 중앙값 계산: mid = (8 + 10) / 2 = 9.
• 중앙값 데이터: 49.

🔎 비교:

• 49 < 55.
• 결론: 55는 49보다 크므로, 오른쪽 범위를 탐색.
• 새로운 탐색 범위: left = 10, right = 10.

4️⃣ 네 번째 탐색

• 탐색 범위: left = 10, right = 10.
• 중앙값 계산: mid = (10 + 10) / 2 = 10.
• 중앙값 데이터: 55.

🔎 비교:

• 55 == 55.
• 결론: 탐색 성공! 🎉
• 55의 위치: 인덱스 10.

💡 결론

• 최대 연산 횟수: log₂(16) = 4.
• 실제 탐색 연산: 4번 만에 완료!
• 전제 조건: 데이터는 오름차순 정렬되어 있어야 함.

 

✅ 다음 게시글에서 예제 문제로 더 자세히 이해해보도록 하겠습니다!

[JAVA][Baekjoon] 1300번 K번째 수 🌟🌟🌟🌟🌟

 

[JAVA][Baekjoon] 1920번 수 찾기

[JAVA][Baekjoon] 2343번 기타 레슨 🌟