[알고리즘 이론] 이진 탐색 알고리즘

이진 검색 알고리즘이란?

: 오름차순으로 정렬된 리스트에서 특정한 값(X)의 위치를 찾는 알고리즘

가장 쉬운 예시로 책 페이지를 찾는 경우를 생각할 수 있다.

선생님이 168페이지를 피라고 말씀하신다면, 우리는 우선 가지고 있는 책을 반으로 갈라 페이지를 확인할 것이다. 

펼친 페이지가 168페이지보다 크다면 더 앞의 페이지를 확인할 것이고, 168페이지보다 적다면 더 뒤의 페이지를 확인할 것이다.

이런 방식으로 임의의 중간값을 설정하여 목표값보다 큰지 작은지 판별하며 범위를 줄여나가는 탐색방법을 이진 탐색이라고 한다. 

- 장점: 탐색할 때마다 범위가 1/2로 줄어들기 때문에 선형 탐색보다 훨씬 빠르다. (선형탐색 : O(N^2), 이진탐색: O(NlogN))

- 단점: 탐색할 리스트가 오름차순으로 정렬된 경우에만 사용할 수 있다. 

 

 

기본적인 탐색방법은 다음과 같다. 

1. 리스트의 중앙값(arr[mid])을 선택하여 그 값과 찾고자 하는 값의 크고 작음을 비교한다.

2. 만약 중앙값(arr[mid])이 찾는값(X)보다 크면, 중앙값 이후의 범위는 탐색할 필요가 없으므로 범위의 최대 인덱스(high)을 중앙값 - 1(mid - 1)로 초기화한다.

- if (arr[mid] > X) high = arr[mid] - 1;

3. 만약 중앙값이 찾는값(X)보다 작으면, 중앙값 이전의 범위는 탐색할 필요가 없으므로 범위의 최소 인덱스(low)을 중앙값 + 1(mid + 1)로 초기화한다.

- if (arr[mid] <= X) low  = arr[mid] + 1;

4. 새로운 범위에서 탐색을 계속 한다....

5. 탐색을 반복하다가 최소 인덱스가 최대 인덱스보다 크거나 같아지면 탐색을 종료한다. 

- while(high <= low)

 

 

의사코드

BinarySearch(arr[0...N-1], X, low, high){ // 탐색할 리스트, 목표값, 최소인덱스, 최대인덱스
   low = 0
   high = N - 1
   
   if (high <= low)
      return -1 // not found
   mid = (low + high) / 2
   if (arr[mid] > X) // 중앙값보다 목표값이 더 작다면
      return BinarySearch(arr, X, low, mid - 1) // 탐색 범위를 low ~ mid-1로 줄여 재탐색
   else if (arr[mid] < X) // 중앙값보다 목표값이 더 크면
      return BinarySearch(arr, X, mid + 1, high) // 탐색 범위를 mid + 1 ~ high로 줄여 재탐색
   else // 중앙값과 목표값이 같다면
      return mid // found
}

 

 

이진검색 알고리즘 활용 문제 (완료)

이진검색을 사용하는 포인트

- 주어진 input 값의 범위가 '10억'에 가까운 것 => 일반적인 탐색으로는 해결하기 힘들 것.

- 풀이 하는 방법은 조합 전체를 구하지 말고, 문제에서 요구하는 답 자체를 어떻게 추정할 수 있는지를 생각하기.

 

 

1. 백준 1654 랜선자르기

- 문제 : www.acmicpc.net/problem/1654 

- 풀이 : ar-tec.tistory.com/48

 

2. 백준 2805 나무자르기

- 문제 : www.acmicpc.net/problem/2805

- 풀이 : ar-tec.tistory.com/49

 

3. 백준 2110 공유기 설치

- 문제 : www.acmicpc.net/problem/2110

- 풀이 : ar-tec.tistory.com/51

 

4. 백준 10815 숫자 카드

- 문제 : www.acmicpc.net/problem/10815

- 풀이 : ar-tec.tistory.com/52

 

5. 프로그래머스 고득점KIT LEVEL3 입국심사

- 문제 : programmers.co.kr/learn/courses/30/lessons/43238

- 풀이 : ar-tec.tistory.com/53

 

6. 프로그래머스 고득점KIT LEVEL4 징검다리

- 문제 : programmers.co.kr/learn/courses/30/lessons/43236

- 풀이 : ar-tec.tistory.com/54

 

 

 

 

참고

-ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%EA%B2%80%EC%83%89_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

- youtu.be/Vfg6-AWGsCw