#01. 이분탐색(Binary Search), 이진탐색

• 오름차순으로 정렬된 리스트에서 특정 값의 위치를 찾는 알고리즘 (이미 정렬되어 있어야 함)
• 모든 값을 순회해야 하는 일반적인 탐색보다 더 빠르다
• 중앙값을 찾는 값과 비교
• left, mid, right 값으로 탐색 -> mid = (left+right)/2

 

(중앙값) > (찾는값)

• 중앙값 기준으로 왼쪽(작은 부분) 탐색
• left -> mid+1

(중앙값) < (찾는값)

• 중앙값 기준으로 오른쪽(큰 부분) 탐색
• right -> mid-1

---

• 반복문을 이용하는 방법

#include <stdio.h>

int main(void) {

	int N;
	int result = 0;

	int A[10] = { 2, 3, 5, 7, 8, 9, 11, 14, 16};

	scanf("%d", &N);
	int left = 0, right = 9;

	while (left <= right) {
		int mid = (left + right) / 2;

		if (A[mid] > N)
			right = mid - 1;
		else if (A[mid] < N)
			left = mid + 1;
		else
		{
			result = mid;
			break;
		}
	}

	printf("%d\n", result);
	return 0;
}

 

• 재귀함수를 이용하는 방법

int BinarySearch(int arr[], int N, int left, int right) {

	if (left > right)
		return -1;

	int mid = (left + right) / 2;

	if (arr[mid] == N)
		return mid;

	else if (arr[mid] > N)
		return BinarySearch(arr, N, left, mid - 1);
	
	else
		return BinarySearch(arr, N, mid + 1, right);
}

 

---

※ 참고한 사이트 ※

 

cjh5414.github.io/binary-search/

이진 탐색(Binary Search) 알고리즘 개념 이해 및 추가 예제

 

wootool.tistory.com/62

[알고리즘] 이분 탐색