Algorithm - Binary search

1. What is binary search?

 이진 탐색(Binart search)은 정렬된 배열안에서 특정 값을 찾아내는 알고리즘이다. 배열의 원소들 중에서 중간값을 찾아서 1) 찾고자 하는 값보다 클 경우, 타켓 값은 중간 값을 기준으로 왼쪽에 위치하고, 2) 작을 경우, 타켓 값은 중간 값을 기준으로 오른쪽에 위치한 것을 알 수 있다. 동일한 방법으로 다시 중간의 값을 선택하고 비교한다. 해당 값을 찾을 때까지 이 과정을 반복한다.

 

2. Example of binary search

List = {1, 2, 3, 4, 5, 6, 7}, Target = {1}

시작점 인덱스는 0, 종점 인덱스는 6일 경우 중간 인덱스는 (시작점 인덱스 + 종점 인덱스) / 2 = 3이다. 

• List[3]와 target 값이 같은지 확인했지만, 다르다는 것을 확인하였으며, List[2]가 target보다 크다는 것도 확인했다.
  이는 target 값은 중간 인덱스보다 앞에 위치해 있음을 짐작할 수 있다.
• 따라서 검색 범위를 [0, 6]에서 [0, 3)로 축소할 수 있다.

List = {1, 2, 3}

시작점 인덱스는 0, 종점 인덱스는 2이며, 중간 인덱스는 (시작점 인덱스 + 종점 인덱스) / 2 = 1이다.

• List[1]와 target 값이 같은지 확인했지만, 다르다는 것을 확인하였으며, List[1]가 target보다 크다는 것도 확인했다.
  이는 또 다시 target 값은 중간 인덱스보다 앞에 위치해 있음을 짐작할 수 있다.
• 따라서 다시 검색 범위를 [0, 3)에서 [0, 1)으로 축소 할 수 있다.

List = {1}

시작점 인덱스는 0, 종점 인덱스는 0이기 때문에 종점 인덱스는 0이다.

•  드디어 마지막으로 List[0]와 target 값이 동일한지를 확인하였고, 동일함을 확인되어 target 값이 위치한 인덱스를 반환함으로써 해당 메서드는 종료된다.
• 만약 target값이 해당 배열에 존재하지 않다는 것이 확인되면 -1을 반환하는 동시에 프로그램은 종료된다.

 

3. Binary search source code

3.1. General Infinite Loop

private static int getIndex(int[] list, int begin, int end,int target) {
		while(begin<=end) {
			int mid = (begin+end)/2;
			
			if(list[mid]==target)
				return mid;
			else if(list[mid]>target)
				begin = mid+1;
			else
				end = mid-1;
		}
		
		return -1;
	}

3.2. Recursion

private static int getIndex(int[] list, int begin, int end, int target) {
		// ** Base case
		if(begin>=end)
			return -1;
		
		// ** Recursion case
		int mid = (begin+end)/2;
		if(list[mid]==target)
			return mid;
		else if(list[mid]>target) 
			return getIndex(list, begin, mid-1, target);
		else
			return getIndex(list, mid+1, end, target);
}

 

이진 탐색(Binary search)이란 이름이 붙여진 이유는 처음에 N개 크기의 배열에서 단계가 하나씩 지나감에 따라 탐색할 배열의 크기가 반씩 줄어들기 때문이다. 이진 탐색(Binary search)은  정렬된 데이터에서 특정한 값을 찾고자할 때 O (logN)의 성능으로 빠르게 값을 찾을 수 있는 장점이 있다.