[알고리즘] 이진 탐색(Binary Search)과 매개변수 탐색(Parameter Search)

Reference

이것이 취업을 위한 코딩 테스트다 with 파이썬, 한빛미디어, 나동빈 지음

📌 탐색(Search)

• 탐색(Search): 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
• 어떤 정수형 자료가 10개 담여있는 배열과 목표값인 target이 주어졌을 때 배열에 target이 존재하는지 확인하기 위해서는?

int[] arr = {93, 12, 39, 88, 7, 13, 53, 20, 53, 27}
int target = 13;

• 수열에서의 탐색 문제는 아래와 같은 질문을 던진다
  • target이 존재하는가?
  • target 이상, 이하, 초과, 미만의 값이 존재하는가?
  • target과 가장 인접한 값은 무엇인가?
• 어떤 수열이 주어졌을 때 순차적으로 값이 존재하는지 탐색하면 최악의 경우 O(N)의 시간이 걸린다.
• 만약 수열이 정렬되어 있다면? 이진 탐색(Binary Search)을 통해 더 빠르게 탐색을 할 수 있게 된다.

📌 순차 탐색(Sequential Search)

• 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법
• 주로 정렬되지 않은 데이터에서 탐색을 해야할 때 순차 탐색을 이용한다.
• 데이터가 아무리 많더라도 시간만 충분하다면 무조건 원하는 값을 찾을 수 있는 탐색 방법이다.
• 데이터의 개수가 총 N개일 때 최악의 경우 N번의 비교 연산이 필요하므로 최악 시간 복잡도는 $O(N)$

for (int i = 0; i < arr.length; i++) {
	if (arr[i] == target) {
		return i + 1; // i + 1번째 위치에 찾는 데이터가 있다, i번 인덱스에 찾는 데이터가 있다
	}
}

📌 이분 탐색(Binary Search)

• 정렬이 보장되는 배열에서 기준 X를 가지고 범위를 이분(X 미만, 초과)하면서 탐색하는 방법: $O(log_2N)$
  • 이미 정렬되어 있는 데이터에서만 사용할 수 있음!!!
  • 탐색 범위를 절반씩 좁혀가며 탐색: $log_2N$에 비례. 즉, 한 번 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어든다
• 3개의 변수가 필요: L, R, mid
  • 시작점 L: 탐색할 가치가 있는 범위의 왼쪽 끝
    • 중간점이 찾으려는 값 보다 작으면 L을 mid + 1로 땡겨온다
  • 끝점 R: 탐색할 가치가 있는 범위의 오른쪽 끝
    • 중간점이 찾으려는 값 보다 크면 R을 mid - 1로 땡겨온다
  • 중간점 mid: 찾으려는 데이터와 비교할 대상값, (L + R) / 2
• 탐색 범위가 큰 상황에서의 탐색을 가정하는 문제가 많다. 탐색 범위가 1,000만 단위를 넘어가면 이진 탐색과 같은 $O(logN)$과 같은 속도를 내는 알고리즘을 떠올려야 한다.

// 크기가 10인 정렬된 배열이 주어짐, X = 63 보다 작은 값은 몇개?
int[] arr = {5, 10, 11, 18, 19, 38, 58, 72, 87, 92}
int X = 63;

1. mid= (L + R) / 2 = (0 + 9) / 2 = 4
2. A[4] = 19, 기준 X 보다 작으니 오른쪽을 탐색
3. mid = (L + R) / 2 = (5 + 9) / 2 = 7
4. A[7] = 72, 기준 X 보다 크니 왼쪽을 탐색
5. mid = (L + R) / 2 = (5 + 6) / 2 = 5
6. A[5] = 38, 기준 X 보다 작으니 오른쪽을 탐색
7. A[6] = 58 만 탐색할 가치가 있는 값이 됨. 탐색을 종료
8. result = 6 이므로 A[6]은 X 이하 중 제일 큰값, X이하의 숫자가 6개

이분 탐색의 시간 복잡도

• 길이가 N인 배열이 주어졌을 때 탐색하는 구간 [L, R] 이 계속 절반으로 좁아지게 된다.
  • 구간의 길이: N ->N / 2 -> N / 4 -> N / 8 -> … -> 2 -> 1
• 즉, 총 비교 횟수는 구간의 변화 횟수인 $O(logN)$ 만에 탐색이 완료된다.
  • N = 10만($10^6$) 이면, $O(log10^6)$ 은 약 16

이분 탐색의 전형적인 코드

• 반복문을 이용한 이분 탐색

	static int binarySearch(int[] arr, int target, int L, int R) {
		while (L <= R) {
			int mid = (L + R) / 2;

			if (arr[mid] == target) {
				return mid;
			}

			if (arr[mid] <= target) { // 기준값이 찾으려는 데이터 보다 작으니 L을 mid + 1로 땡겨온다
				L = mid + 1;
			} else { // 기준값이 찾으려는 데이터 보다 크니 R을 mid - 1로 땡겨온다
				R = mid - 1;
			}
		}

		return -1; // 존재하지 않음
	}

• 재귀 호출을 이용한 이분 탐색

	static int binarySearch(int[] arr, int target, int L, int R) {
		if (L > R) {
			return -1; // 존재하지 않음
		}

		int mid = (L + R) / 2;
		if (arr[mid] == target) {
			return mid;
		}

		if (arr[mid] > target) { // 중간값이 찾으려는 값 보다 크면, R을 mid - 1로 땡겨온다
			return binarySearch(arr, target, L, mid - 1);
		} else { // 중간값이 찾으려는 값 보다 작으면, L을 mid + 1로 땡겨온다
			return binarySearch(arr, target, mid + 1, R);
		}
	}

이분 탐색을 할 때 주의할 점

• 반드시 정렬된 배열에서 이분 탐색을 진행한다.
• L, R, mid 변수의 정의를 올바르게 설정하고 이해한다.
  • 부등호를 잘못 설정하거나, 범위를 잘못 설정하는 경우 탐색이 올바르지 않게 진행된다.

📌 매개 변수 탐색(Parametric Search)

• 매개 변수 탐색은 최적화 문제를 결정 문제(Yes or No)로 바꾸어서 해결하는 기법
  • 반드시 정렬된 배열에서 사용해야 하는 탐색 기법
    • 기준값의 왼쪽 구간과 오른쪽 구간은 Yes or No로 일정하게 채워져야 한다.
  • 원하는 조건을 만족하는 가장 알맞은 값(가장 큰 값 or 가장 작은 값)을 찾는 문제
• 어떤 조건이 주어지고 조건에 맞는 최대값, 최소값을 구하는 문제에 적용해볼 가치가 있다.
• 매개 변수 탐색을 적용한 문제풀이

매개 변수 탐색을 할 때 주의할 점

• 결정 문제(Yes or No)로 풀 수 없는 경우인데 이분 탐색을 하는 경우
• L, R, mid 변수의 정의를 올바르게 설정하고 이해한다.
  • 부등호를 잘못 설정하거나, 범위를 잘못 설정하는 경우 탐색이 올바르지 않게 진행된다.

📌 트리 자료구조와 이진 탐색

• 데이터베이스와 같이 수 많은 데이터를 저장하는 구조는 트리(Tree) 자료구조를 이용해 항상 데이터가 정렬되어 있도록 설계된다.
  • 이진 탐색과 유사한 방법을 이용해 탐색을 항상 빠르게 수행하도록 설계됨
• 트리 자료구조의 특징
  • 부모 노드와 자식 노드의 관계로 표현
  • 최상단 노드(최상위 조상)를 루트 노드라 표현
  • 최하단 노드(최하위 노드)를 단말 노드라 표현
  • 트리에서 일부를 떼어내도 트리 구조이며 이를 서브 트리라 한다
  • 파일 시스템과 같이 계층적이고 정렬된 데이터를 다루기에 적합

이진 탐색 트리 (Binary Search Tree)

• 이진 탐색이 동작할 수 있도록 고안된 효율적인 탐색이 가능한 트리 자료구조
• 이진 탐색 트리의 특징
  • 부모 노드보다 왼쪽 자식 노드가 작다
  • 부모 노드보다 오른쪽 자식 노드가 크다
  • 즉, 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드