이진탐색 알고리즘

이진탐색 알고리즘

- 순차 탐색 보다 훨씬 좋은 성능을 보인다.

- 배열이 정렬되어 있어야 한다는 제약이 따른다.

(당연하다. 절반씩 나누어 탐색을 나아가는 알고리즘이기때문에 정렬이 되어있어야 한다.)

- 절반씩 나누어 탐색을 나아가는 알고리즘(대소비교를 통해 왼쪽 오른쪽을 찾아나간다.)

 

포인트는 last에 mid -1을 해주는것과 first에 mid +1을 해주는 것이다.

first와 last가 역전될 때까지 탐색을 지속적으로 시켜주기위해서 반드시 필요한 부분이다.

 

이진 탐색 알고리즘 최악의 경우 시간 복잡도 구해보기

- 시간 복잡도 계산을 위한 핵심 연산은 == 연산자이다!

=> if(target == ar[mid]) 에서 ==이다.

왜냐하면 여기서 true를 반환하게되면 return mid를 실행하게 되며 함수가 종료되기 때문이다.

그래서 다른 연산자들은 ==에게 종속적일수밖에 없기 때문에 ==가 기준이다.

 

** 최악의 경우

데이터의 수가 n개 일경우 3을 찾을때, 근데 3이 안들어있는경우 일것이다. 

n개일때 1번 ,

n/2개 일때 1번

n/4일때 1번

'

'

1개가 남을때 1번

 

언제까지 진행되는가?

n이 얼마인지 결정되지 않았으니 도데체 몇 번의 비교연산이 진행되는지 알 수 가 없다.

 

n이 1이 몇번 반으로 나눠야 하는가?

n * (1/2)k = 1

 

T(n) =

 

int BSearch(int ar[], int len, int target)
{
	int first = 0; // 탐색 대상의 시작 인덱스
	int last = len-1; //탐색 대상의 마지막 인덱스
	int mid;

	while(first <= last)
	{
		mid = (first + last) / 2; // 탐색 대상의 중앙을 찾는다.
		if(target == ar[mid]) // 중앙에 저장된 것이 타겟이라면
		{
			return mid; //탐색완료!
		}
		else  // 타겟이 아니라면 탐색 대상을 반으로 줄인다.
		{
			if(target < ar[mid])
			{
				last = mid -1; //왜 -1을 했나?
			}
			else
			{
				first = mid +1; // 왜 +1을 했나?
			}
		}
	}
	return -1; // 찾지 못했을때 -1반환
}