[2022 겨울학기] 7주차 - 이분탐색

1. 이분탐색(Binary Search)이란?

탐색 범위를 절반씩(두 부분으로 나누어서) 줄여 가며 원하는 값을 찾는 방식

이분 탐색을 실시하기 위해선 정렬된 배열이나 벡터가 필요하다

시간복잡도 또한 탐색 범위가 절반씩 줄어든다. -> O(logN)

 

2. 동작 원리

-이분 탐색

배열이나 벡터를 정렬한다

left, right값(범위의 최소, 최대)으로 mid값을 설정한다

mid값과 구하고자 하는 값(ans)를 비교한다

mid < ans --> mid+1        mid > ans --> mid-1

ans를 찾을 때까지 반복

 

-결과값

구하고자하는 값을 찾았을 때 값을 리턴한다

최적의 해를 찾는 경우 left <= right까지 반복한다

목표값을 찾지 못한 경우 left > right이 되므로 종료된다

 

 

3. 코드

int arr[100005];

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

		if (find == arr[mid]) {
			return 1; //수가 존재하면 1 반환
		}
		else if (find > arr[mid]) {
			left = mid + 1;
		}
		else { //find < arr[mid]
			right = mid = 1;
		}

		return 0; //값을 찾지 못함(수가 존재하지 않음), 0 반환
	}
}

int arr[100005];

int binarySearch(int left, int right, int find) {

	int mid;
	mid = (left + right) / 2;

	if (find == arr[mid])
		return 1;
	if (left > right)
		return 0;

	if (arr[mid] < find)
		return binarySearch(mid + 1, right, find);
	else
		return binarySearch(left, mid - 1, find);

}

 

※공부 중 작성한 내용이기에 틀린 부분이 있을 수도 있습니다!