[4] 이진탐색

 

1. 이진탐색 알고리즘이란?

순차탐색

• 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법

이진탐색

정렬되어있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법

• 시작점, 끝점, 중간점을 이용하여 탐색범위를 정함

예시

정렬된 10개의 데이터 중에서 값이 4인 원소를 찾기

0	1	2	3	4	5	6	7	8	9
0	2	4	6	8	10	12	14	16	18

[1단계] 시작점 : 0 , 끝점 : 9 , 중간점 : 4 (소수점 이하 제거)

0	1	2	3	4	5	6	7	8	9
0	2	4	6	8	10	12	14	16	18

1. 중간점에 위치한 값인 8과 찾고자하는 값 4를 비교
2. 찾고자하는 값 4 < 중간점 값 8 ⇒ 중간점 이상의 값들을 볼 필요가 없음

[2단계] 시작점 : 0 , 끝점 : 3 , 중간점 : 1 (소수점 이하 제거)

0	1	2	3	4	5	6	7	8	9
0	2	4	6	8	10	12	14	16	18

1. 중간점에 위치한 값인 2와 찾고자하는 값 4를 비교
2. 찾고자하는 값 4 > 중간점 값 2 ⇒ 중간점 이하의 값들을 볼 필요 없음

[3단계] 시작점 : 2 , 끝점 : 3 , 중간점 : 2 (소수점 이하 제거)

0	1	2	3	4	5	6	7	8	9
0	2	4	6	8	10	12	14	16	18

1. 중간점 위치한 값 4와 찾고자하는 값 4를 비교
2. 일치하므로 탐색을 마침 ⇒ 4는 인덱스 2에 위치

 

2. 이진 탐색의 시간 복잡도

• 단계마다 탐색범위를 2로 나누는 것과 동일 ⇒ 연산횟수는 $$ log_xN $$ 에 비례
• 예시
  • 초기 데이터 개수가 32개 일 때, 이상적인 경우
    • [1단계] 16개가량의 데이터만 남음
    • [2단계] 8개가량의 데이터만 남음
    • [3단계] 4개가량의 데이터만 남음
• 이진탐색은 탐색 범위를 절반씩 줄임

시간 복잡도

$$ O(logN) $$

 

3. 이진탐색 소스코드

1) 재귀적 구현

Python

# 이진 탐색 소스코드 구현 (재귀함수)
def binary_search(array, target, start, end):
	if start > end:
		return None
	mid = (start + end) // 2
	# 찾은 경우 중간점 인덱스 반환
	if array[mid]==target:
		return mid
	# 중간점의 값보다 찾고자하는 값이 작은 경우 왼쪽 확인
	elif array[mid] > target:
		return binary_search(array, target, start, mid-1)
	else:
		return binary_search(array, target, mid+1, end)

import sys

# n(원소의 개수)과 target(찾고자하는 값) 입력받기
n, target = list(map(int,sys.stdin.readline().split()))
# 전체 원소 입력 받기
array=list(map(int,sys.stdin.readline().split()))

# 이진탐색 수행결과 출력
result=binary_search(array, target, 0, n-1)
if result==None:
	print('원소가 존재하지 않습니다')
else:
	print(result+1)

Java

public class Main {
	// 이진탐색 소스코드 구현
	public static int binarySearch(int[] arr, int target, int start, int end){
		while(start <= end) {
			int mid = (start+end)/2;
			// 찾은 경우 중간점 인덱스 반환
			if (arr[mid] == target) return mid;
			// 중간점의 값보다 찾고자하는 값이 작은 경우 왼쪽 확인
			else if (arr[mid] > target) end = mid-1;
			// 중간점의 값보다 찾고자하는 값이 큰 경우 오른쪽 확인
			else start = mid+1;
		}
		return -1;
	}
	// 메인 코드 (생략)

		// 이진 탐색 수행 결과 출력
		int result = binarySearch(arr,target, 0, n-1);
		if (result == -1) {
			System.out.prinln("원소가 존재하지 않습니다.");
		}
		else {
			System.out.println(result+1)
		}
	
	}
}

 

2) 코테 문제 해결을 위한 라이브러리

• bisect_left(a, x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스를 반환
• bisect_right(a, x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른족 인덱스를 반환

1) 예시

1 - 2 - 4 - 4 - 8

• bisect_left(a, 4)
• bisect_right(a, 4)

from bisect import bisect_left, bisect_right

a = [1, 2, 4, 4, 8]
x = 4

print(bisect_left(a,x))   # 2
print(bisect_right(a,x))  # 4

 

(2) 값이 특정 범위에 속하는 데이터 개수 구하기

from bisect import bisect_left, bisect_right

# 값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수
def count_by_range(a, left_value, right_value):
	right_index = bisect_right(a, right_value)
	left_index = bisect_left(a, left_value)
	return right_index - left_index

# 배열 선언
a = [1,2,3,3,3,3,4,4,8,9]

# 값이 4인 데이터 개수 출력
print(count_by_range(a, 4, 4))      # 2

# 값이 [-1,3] 범위에 있는 데이터 개수 출력
print(count_by_range(a, -1, 3))     # 6

 

4. 파라메트릭 서치 (Parametric Search)

최적화 문제를 결정 문제 (’예’ 혹은 ‘아니오’)로 바꾸어 해결하는 기법

• 예시 : 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제
• 파라메트릭 서치 문제 : 이진탐색을 이용하여 해결

 

---

출처 : https://www.youtube.com/watch?v=94RC-DsGMLo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=5