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

2025. 1. 6. 21:39·CS/알고리즘
728x90
반응형

📌  이진 탐색이란?

이진 탐색(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번째 수 🌟🌟🌟🌟🌟

https://www.acmicpc.net/problem/1300 📌 접근 방식처음엔 이걸 이진 탐색으로 풀 생각조차 하지 못했다.. 전혀 이 문제를 보고 이진 탐색을 떠올릴 수 없었다...배열 B의 크기가 매우 커지기 때문에 이 배

nyeroni.tistory.com

 

 

[JAVA][Baekjoon] 1920번 수 찾기

https://www.acmicpc.net/problem/1920📌 접근 방식1️⃣ 이진 탐색 사용배열 A를 정렬하여 이진 탐색의 전제 조건(정렬된 배열)을 충족.M개의 수를 각각 A에 대해 이진 탐색을 사용해 존재 여부를 확인.이

nyeroni.tistory.com

 

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

https://www.acmicpc.net/problem/2343📌 접근 방식이 문제는 주어진 강의들을 최소한의 블루레이 크기로 M개의 블루레이에 나누어 담는 문제이다.중요한 점은 블루레이에 담는 강의의 순서가 바뀌면 안

nyeroni.tistory.com

 

 

 

 

 

 

728x90
반응형
저작자표시 비영리 변경금지 (새창열림)

'CS > 알고리즘' 카테고리의 다른 글

[알고리즘] 정수론 : 소수(Prime number) 구하기  (0) 2025.01.09
[알고리즘] 그리디 알고리즘(Greedy Algorithm)  (1) 2025.01.07
[알고리즘] 너비 우선 탐색 : BFS(Breadth-First-Search)  (0) 2025.01.06
[알고리즘] 깊이 우선 탐색 : DFS(Depth-First-Search)  (0) 2025.01.04
[알고리즘] 기수 정렬(Radix Sort)이란?  (0) 2025.01.03
'CS/알고리즘' 카테고리의 다른 글
  • [알고리즘] 정수론 : 소수(Prime number) 구하기
  • [알고리즘] 그리디 알고리즘(Greedy Algorithm)
  • [알고리즘] 너비 우선 탐색 : BFS(Breadth-First-Search)
  • [알고리즘] 깊이 우선 탐색 : DFS(Depth-First-Search)
예롱메롱
예롱메롱
  • 예롱메롱
    예롱이의 개발 블로그
    예롱메롱
  • 전체
    오늘
    어제
    • 전체보기 (274)
      • 프로젝트 (35)
        • Wedle (12)
        • 인스타그램 클론 코딩 (13)
        • 스프링 부트와 AWS로 혼자 구현하는 웹 서비스 (10)
      • 인프런 Spring 강의 정리 (79)
        • 스프링 입문 - 코드로 배우는 스프링 부트, 웹 .. (7)
        • Spring 핵심 원리 - 기본편 (9)
        • 모든 개발자를 위한 HTTP 웹 기본 지식 (8)
        • 자바 ORM 표준 JPA 프로그래밍 - 기본편 (11)
        • 실전! 스프링 부트와 JPA 활용1 - 웹 애플리.. (6)
        • 실전! 스프링 부트와 JPA 활용2 - API 개.. (5)
        • 실전! 스프링 데이터 JPA (7)
        • 스프링 MVC 1편 - 백엔드 웹 개발 핵심 기술 (7)
        • 스프링 MVC 2편 - 백엔드 웹 개발 활용 기술 (11)
        • 실전! Querydsl (8)
      • Cloud (3)
      • Spring (6)
        • spring boot (5)
        • 소셜로그인 (1)
      • Docker (2)
      • DevOps (0)
      • Coding Test (114)
        • Programmers (37)
        • Baekjoon (76)
      • KB It's Your Life 6기 (1)
      • CS (18)
        • 알고리즘 (13)
        • 컴퓨터 구조 (1)
        • Operating System (0)
        • Network (0)
        • Database (4)
      • git (1)
      • Language (15)
        • Java (5)
        • C++ (6)
        • Python (4)
    • GITHUB GITHUB
    • INSTAGRAM INSTAGRAM
  • hELLO· Designed By정상우.v4.10.3
예롱메롱
[알고리즘] 이진 탐색(Binary Search)
상단으로

티스토리툴바