이분탐색(Binary Search) 알고리즘

개요

이분탐색은 정렬된 데이터에서 검색 범위를 줄여나가며 원하는 데이터를 검색하는 알고리즘이다. 이진 탐색은 탐색을 반복할 때마다 탐색 범위를 반으로 줄인다. 탐색 범위가 1이 되는 최종 탐색 횟수를 k라고 하면,

1. 한 번 비교할 때의 범위는 n/2

2. 두 번 비교할 때의 범위는 n/4

3. 세 번 비교할 때의 범위는 n/8

...

k. k 번 비교할 때의 범위 n/(2^k)는 = 1 이고, k = log₂N 이다. 따라서 이진 탐색의 시간 복잡도는 O(logN)이 된다.

 

설명

0	1	2	3	4	5	6	7	8	9
2	5	6	9	12	13	14	18	20	23

위와 같이 정렬되어 있는 배열이 있을 때, 20을 찾는다고 가정해보자. 만약 순차탐색을 하면 0번째 인덱스, 1번째 인덱스, 2번째 인덱스 ... 를 순서대로 찾아가면서 9번째 탐색에서 원하는 값을 찾을 수 있을 것이다.

0	1	2	3	4	5	6	7	8	9
2	5	6	9	12	13	14	18	20	23

이분탐색을 이용한다면 제일 왼쪽 인덱스 0과 제일 오른쪽 인덱스 9를 이용하여 가운데 인덱스((0+9)/2 = 4)와 값(12)를 구한다. 이때 구하려는 값 20보다 12가 작으므로 왼쪽 인덱스를 5로 변경해준다.

0	1	2	3	4	5	6	7	8	9
2	5	6	9	12	13	14	18	20	23

마찬가지로 왼쪽 인덱스와 오른쪽 인덱스를 이용하여 가운데 인덱스((5+9)/2 = 7)와 값(18)을 구한다. 이때 구하려는 값 20보다 작으므로 또다시 왼쪽 인덱스를 8으로 변경해준다.

0	1	2	3	4	5	6	7	8	9
2	5	6	9	12	13	14	18	20	23

왼쪽 인덱스와 오른쪽 인덱스를 이용하여 가운데 인덱스((8+9)/2 = 8)와 값(20)을 구한다. 원하는 값을 찾았으므로 탐색을 종료한다.

 

구현

import java.util.*;

class BinarySearch{
	public static void main(String[] args) throws Exception{
		int[] arr = {1, 4, 3, 9, 10, 12, 20, 22, 0, 13}; // 무작위 데이터로 입력된 배열
		Arrays.sort(arr); // 배열을 오름차순으로 정렬한다 
		
		int N = 13; //찾는 값 
		
		//초기 인덱스는 가장 끝 쪽으로 초기화 한다
		int left = 0;
		int right = arr.length - 1;
		int mid = 0; //left와 right의 가운데 인덱스
		
		while(left <= right) { //왼쪽 인덱스가 오른쪽 인덱스보다 커지면 탐색을 종료한다
			mid = (left + right)/2;
			
			if(N == arr[mid]) { //원하는 값을 찾았다면 탐색을 종료한다
				break;
			}else {
				if(N < arr[mid]) { //원하는 값보다 현재 인덱스의 값이 크다면 오른쪽 범위를 없애준다
					right = mid - 1;
				}else { //원하는 값이 현재 인덱스의 값보다 작다면 왼쪽 범위를 없애준다
					left = mid + 1;
				}
			}
		}
		
		System.out.print(mid+"번째 인덱스에서 값 발견");
    }
}

 

참고

https://minhamina.tistory.com/127