이분 탐색(Binary Search)

이분 탐색(Binary Search)

정렬된 배열에서 특정 값을 검색할 때 사용하는 알고리즘

탐색을 진행하기 전에 반드시 배열이 정렬된 상태이어야 한다.

 

시간복잡도 : O(logN)

한번 탐색을 진행할 때마다 탐색의 범위가 반으로 줄어들기 때문에 선형 탐색에 비해 속도가 빠르다.

 

 

알고리즘 : 

1. 이분 탐색 범위의 시작 위치를 가리키는 포인터를 pl, 마지막 위치를 가리키는 포인터를 pr로 설정한다.

   그리고 탐색 범위의 가운데를 가리키는 포인터를 pc로 설정한다.

• arr[pc] = key 이면, 탐색하려는 값을 찾았으므로 이분탐색을 종료한다.

• arr[pc] < key 이면, pl을 pc보다 하나 오른쪽으로 갱신한다. -> pl = pc + 1

• arr[pc] > key 이면, pr을 pc보다 하나 왼쪽으로 갱신한다. -> pr = pc - 1

2. pl과 pr이 서로 교차되지 않을 때까지(pl <= pr) 범위를 좁혀가며 탐색을 반복한다.

 

 

[예제]

다음과 같은 정렬된 배열 arr = {2, 5, 8, 10, 13, 14, 19, 20, 22, 30, 50} 가 있다.

이 배열에서 key = 10을 찾는 과정을 이제부터 살펴보자.

 

먼저, 이 배열의 첫번째 인덱스인 0이 left에 들어가고, 마지막 인덱스인 10이 right에 들어간다.

left = 0

right = 10

 

 

탐색을 진행할 범위의 왼쪽 끝을 가리키는 pl, 오른쪽 끝을 가리키는 pr을 초기화해준다.

가장 처음에 탐색의 범위는 배열 전체이므로 pl = left, pr = right 이 들어간다.

pc 는 탐색을 진행할 범위의 가운데를 가리키도록 한다.

범위의 시작위치가 pl, 끝위치가 pr 이므로 pc = (pl + pr) / 2 로 구할 수 있다.

 

이제 arr[pc] 와 key값을 비교한다.

• arr[pc] = key 이면, 탐색하려는 값을 찾았으므로 이분탐색을 종료한다.

• arr[pc] < key 이면, pl을 pc보다 하나 오른쪽으로 이동한다. -> pl = pc + 1

• arr[pc] > key 이면, pr을 pc보다 하나 왼쪽으로 이동한다. -> pr = pc - 1

 

현재 pc 위치에 있는 값은 14 이므로 arr[pc] = 14 이다. 14와 key = 10을 비교했을 때, key보다 크므로

pr = pc - 1 = 4 가 된다. 

pl = 0, pr = 4 이므로 탐색 범위가 반으로 줄어들었다.

pc = (0 + 4) / 2 = 2 가 된다.

 

arr[pc] = 8 이 key값인 10보다 작으므로 이번에는 pl 이 pc + 1 위치로 이동한다.

pl = 3, pr = 4, pc = (3 + 4) / 2 = 3

 

arr[pc] = 10 이 key값인 10과 동일하다. 그러므로 이분탐색을 종료하고, pc값을 반환한다. pc = 3

 

 

소스코드 : 

	public int binSearch(int n, int left, int right) {

		int pl = left;
		int pr = right;

		do {

			int pc = (pl + pr) / 2;

			if (arr[pc] == n)
				return pc;

			if (arr[pc] < n)
				pl = pc + 1;
			else
				pr = pc - 1;

		} while (pl <= pr);

		return -1;
	}