[Algorithm] 이분탐색(Binary Search)

개요

 

◎ 이분 탐색이란?

◎ 구현 코드 (Java)

◎ 그림 예시

◎ 사용 목적

◎ 시간 복잡도

◎ 조건

◎ 자바에서 제공하는 메서드

 

 

 

안녕하세요. J4J입니다.

 

이번 포스팅은 이분 탐색에 대해 적어보는 시간을 가져보려고 합니다.

 

 

이분 탐색이란?

 

이분 탐색이란 여러 탐색 기법들 중 하나로 탐색하는 구간을 두 부분으로 나누어 탐색하는 기법입니다.

 

탐색을 위해 탐색하는 구간을 두 부분으로 나누지만 실질적으로 탐색은 한 구간만 선택하여 탐색하고 이 행동을 반복하여 찾고자 하는 값을 도출해 내는 방식입니다.

 

 

구현 코드 (Java)

 

package search;

public class BinarySearch {
	public static void main(String[] args) {
		int[] intArray = new int[]{1, 2, 6, 9, 13, 17, 21, 24, 27};
		
		int target = 6; // 찾으려고 하는 값
		int targetIndex = binarySearch(0, intArray.length-1, target, intArray);
		
		System.out.println(target + "의 인덱스 위치는 " + targetIndex + "입니다."); // 6의 인덱스 위치는 2입니다.
	}
	
	public static int binarySearch(int left, int right, int target, int[] array) {
		if(left > right) { // 왼쪽 인덱스가 오른쪽 인덱스보다 커지면 종료
			return -1;
		}
		
		int mid = (left+right) / 2; // 왼쪽 인덱스와 오른쪽 인덱스의 가운데 인덱스 값 구하기
		
		if(array[mid] == target) { // 가운데 인덱스에 해당하는 값이 찾는 값일 경우
			return mid;
		} else if(array[mid] > target) { // 가운데 인덱스에 해당하는 값이 찾는 값보다 클 경우
			return binarySearch(left, mid-1, target, array);
		} else { // 가운데 인덱스에 해당하는 값이 찾는 값보다 작을 경우
			return binarySearch(mid+1, right, target, array);
		}
	}
}

 

728x90

 

그림 예시

 

 

 

사용 목적

 

이분 탐색을 사용하는 목적은 더 빠른 속도로 탐색을 하기 위해서입니다.

 

가장 기본적인 탐색방법은 for문과 while문이 대표적입니다.

 

이 둘을 사용하여 탐색한다면 첫 인덱스부터 마지막 인덱스까지 모두 탐색해야 되지만 이분 탐색을 사용하여 탐색한다면 한 번의 턴마다 탐색하는 구간이 반으로 줄어들며 탐색을 합니다.

 

예를 들어 배열에 원소가 1024개가 들어있다고 가정하면 for문, while문은 최악의 경우에 1024번 탐색을 해야 되지만 이분 탐색은 다음과 같은 결과가 나옵니다.

 

1. 첫 번째 턴 탐색 대상 원소: 1024개

2. 두 번째 턴 탐색 대상 원소: 512개

3. 세 번째 턴 탐색 대상 원소: 256개

 

.

.

.

 

10. 열 번째 턴 탐색 대상 원소: 2개

11. 열한 번째 턴 탐색 대상 원소: 1개

 

보시는 것과 같이 1024번을 탐색하는 for문, while문과 달리 11번 만에 탐색을 종료하는 모습을 보여줍니다.

 

 

시간 복잡도

 

이분 탐색의 시간 복잡도는 O(logN)입니다.

 

원소가 N개만큼 있다고 가정할 때 턴마다 매번 ½만큼 줄어들고 K번만큼의 턴을 진행했을 때 남은 탐색 대상의 원소가 1개라고 하겠습니다.

 

이럴 경우 N x (½)^K = 1이라는 식이 나오고 N = 2^K라는 값이 나옵니다.

 

시간이 걸린 값은 K값이기 때문에 밑이 2인 로그를 양 변에 씌워주면 logN = K라는 결과가 나옵니다. (이런 결과가 이해가 안되시면 고등학교 수학시간에 배운 지수/로그 파트를 참고해주세요.)

 

 

조건

 

이분 탐색을 사용하기 위한 조건은 정렬이 되어있어야 한다는 것입니다.

 

한 마디로 정렬이 되어있지 않으면 이분 탐색을 사용할 수 없습니다.

 

 

자바에서 제공하는 메서드

 

추가적으로 이분 탐색은 정렬(Sorting)과 같이 자바에서 메서드를 제공해줍니다.

 ※ 자바에서 제공해주는 정렬 메서드가 궁금하다면? [Algorithm] 정렬(Sorting)

 

대표적으로 정렬과 동일하게 Arrays와 Collections가 존재합니다.

 

package search;

import java.util.Arrays;

public class JavaBinarySearch {
	public static void main(String[] args) {
		int[] intArray = new int[]{1, 2, 6, 9, 13, 17, 21, 24, 27};
		
		int target = 6;
		int targetIndex = Arrays.binarySearch(intArray, target);
		
		System.out.println(target + "의 인덱스 위치는 " + targetIndex + "입니다."); // 6의 인덱스 위치는 2입니다.;
	}
}

 

Arrays같은 경우는 구현했던 코드와 동일한 결과를 만들고 싶으면 위의 코드처럼 사용하면 되고 Collections도 Arrays와 사용방법은 동일합니다.

 

 

정리

 

● 이분 탐색은 구간을 두 부분으로 나누며 탐색하는 기법

● O(N)만큼 소요되는 기본적인 탐색기법보다 빠른 O(logN)이라는 시간 복잡도를 가짐

● 정렬되어 있을 경우에만 사용 가능

● 정렬되어 있지 않을 때 사용한다면 정렬할 때 더 오랜 시간이 소모됨

 

이상으로 이분 탐색에 대해 간단하게 알아보는 시간이었습니다.

 

읽어주셔서 감사합니다.