[이것이 취업을 위한 코딩 테스트다 with 파이썬] 5. 이진 탐색

이진 탐색 알고리즘

• 순차 탐색
  • 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법
• 이진 탐색
  • 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
  • 시작점, 끝점, 중간점 이용 -> 탐색 범위 설정

예시

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

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

시간 복잡도

• 단계마다 탐색 범위를 2로 나누는 것과 동일 -> 연산 횟수는 $log_2N$에 비례
• ex. 초기 데이터 개수 32개 -> 이상적으로 1단계 거치면 16개가량의 데이터 남음
  • 2단계 -> 8개가량의 데이터만 남음
  • 3단계 -> 4개가량의 데이터만 남음

=> 이진 탐색: 탐색 범위 절반씩 줄이며, 시간 복잡도: $O(log N)$

---

소스코드

Python - 재귀 함수, 반복문

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

# 반복문
def binary_search(array, target, start, end):
	while start <= end:
    	mid = (start + end) // 2
        
        # 찾은 경우 중간점 인덱스 반환
        if array[mid] == target:
    		return mid
   		# 중간점의 값 < 찾고자 하는 값 -> L 확인
   		elif array[mid] > target:
    		end = mid - 1
    	# 중간점의 값 < 찾고자 하는 값 -> R 확인
    	else:
    		start = mid + 1
    return None

 

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

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

C++ - 반복문 

#include <bits/stdc++.h>
using namespace std;

int binarySearch(vector<int>& arr, int target, int start, int end) {
	while (start <= end) {
    	int mid = (start + end) / 2;
        
        // 찾은 경우 중간점 인덱스 반환
        if (arr[mid] == target) return mid;
        # 중간점의 값 < 찾고자 하는 값 -> L 확인
        else if (arr[mid] > target) end = mid - 1
        # 중간점의 값 < 찾고자 하는 값 -> R 확인
        else start = mid + 1;
    }
    return -1;
}

int n, target;
vector<int> arr;

int main(void) {
	// n(원소의 개수)와 target(찾고자 하는 값) 입력 받기
    cin >> n >> target;
    
    // 전체 원소 입력 받기
    for (int i = 0; i < n; i++) {
    	int x;
        cin >> x;
        arr.push_back(x);
	}
    
    // 이진 탐색 수행 결과 출력
    int result = binarySearch(arr, target, 0, n - 1);
    
    if (result == -1) {
    	cout << "원소가 존재하지 않습니다." << '\n';
    }
    else {
    	cout << result + 1 << '\n';
    }
    return 0;
}

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;
            // 중간점의 값 < 찾고자 하는 값 -> L 확인
            else if (arr[mid] > target) end = mid - 1
            // 중간점의 값 < 찾고자 하는 값 -> R 확인
            else start = mid + 1;
        }
        return -1;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 원소의 개수(n)와 찾고자 하는 값(target) 입력받기
        int n = sc.nextInt();
        int target = sc.nextInt();

        // 전체 원소 입력받기
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        
        // 이진 탐색 수행 결과 출력
        int result = binarySearch(arr, target, 0, n - 1);
        if (result == -1) {
            System.out.println("원소가 존재하지 않습니다.");
        }
        else {
            System.out.println(result + 1);
        }
    }
}

---

라이브러리

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

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

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

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(1, 4, 4))

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

---

파라메트릭 서치(Parametric Search)

• 최적화 문제 -> 결정 문제('예' or '아니오')로 바꿔 해결하는 기법
  • ex. 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제
• 일반적 코딩 테스트에서 파라메트릭 서치 문제 -> 이진 탐색 이용하여 해결

---