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

1. 이진탐색이란?

탐색할 자료를 둘로 나누어 해당 데이터가 있을만한 곳을 탐색하는 방법이다.

탐색 알고리즘 : 순차탐색, 해시구조, 이진탐색트리, 이진탐색 등 계속 반복해서 보자!

 

이미지출처 : blog.penjee.com/binary-vs-linear-search-animated-gifs/

2. 분할 정복 알고리즘과 이진 탐색

• 분할 정복 알고리즘 (Divide and Conquer)
• Divide : 문제를 하나 또는 둘 이상으로 나눈다.
• Conquer : 나눠진 문제가 충분히 작고, 해결이 가능하다면 해결하고 그렇지 않으면 다시 나눈다.

3. 이진탐색을 구현하기 위해서는?

이진 탐색은 데이터가 정렬되어있는 상태에서 진행되어야한다.

 

dataList의 중간값을 findData와 비교해서

• findData > dataList의 중간값
• 중간값 인덱스부터 끝까지 다시 findData찾기

• findData < dataList의 중간값
• 맨 처음부터 끝까지 다시 findData찾기

• 그렇지않다면, findData는 dataList의 중간값이므로 탐색 완료

4. 이진탐색의 시간복잡도

n개의 데이터를 매번 2로 나누어 1이 될때까지 비교연산을 k회 진행한다.

n x 1/2 x 1/2 x 1/2 x ... x 1/2 = 1

n x (1/2)^k = 1

n = 2^k = logn = log2^k

logn = k

n이 1이 되었을 때도 비교연산을 한번 더 수행해주기 때문에 O(logn + 1)이지만 상수는 시간복잡도에 의미가 없으므로 O(logn)이 이진탐색의 시간복잡도이다.

 

5. 구현코드 (자바)

package Concept;

import java.util.Arrays;
/*
 * 이진탐색(이분탐색) : 탐색할 자료를 둘로 나누어 해당 데이터가 있을만한 곳을 탐색하는 방법
 */
public class BinarySearch {

	public static void main(String[] args) {
		int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8 ,9 };
		
		System.out.println(Arrays.toString(arr));
		
		if (binarySearch(arr, 0, arr.length - 1, 4) == 1)
			System.out.println("존재합니다.");
		else 
			System.out.println("존재하지않습니다.");
	}
	
	public static int binarySearch(int[] arr, int start, int end, int data) {
		
		if (start > end) {
			return -1;
		}
		
		int mid = (start + end) / 2;
		
		if (arr[mid] > data) {
			return binarySearch(arr, start, mid - 1, data); // mid번이 data가 아니므로 비교하는 의미없음 -1.
		} else if (arr[mid] < data) {
			return binarySearch(arr, mid + 1, end, data);
		} else {
			return 1;
		}
	}
}