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

이진 탐색 (이분 탐색, Binary Search)

• 데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘
• 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾음
• 기능 : 타깃 데이터 검색
• 특징 : 중앙값 비교를 통한 대상 축소 방식
• 시간 복잡도 : O(longN)
• 오름차순으로 정렬된 데이터 기준
  1. 현재 데이터셋의 중앙값을 선택
  2. 중앙값 > 타깃 데이터 일 때 중앙값 기준으로 왼쪽 데이터셋을 선택
  3. 중앙값 < 타깃 데이터 일 때 중앙값 기준으로 오른쪽 데이터셋을 선택
  4. 위의 과정을 반복
• 내림차순일 경우 조건을 반대로 하여 과정을 반복
• 데이터의 삽입, 삭제가 많을 경우에는 적합하지 않아, 주로 고정된 데이터에 대한 탐색에 적합

 

구현방법

1. 반복문을 이용한 구현

	static int binarySearch(int key, int low, int high) {
		int mid;
		
		while(low <= high) {
			mid = (low + high) / 2;
			
			if(key == arr[mid]) {
				return mid; // 원하는 값 위치 반환
			} else if(key < arr[mid]) {
				high = mid - 1;
			} else {
				low = mid + 1;
			}
		}
		
		return -1; // 원하는 값 없음
	}

 

2. 재귀를 이용한 구현

	static int binarySearch(int key, int low, int high) {
		int mid;
		
		if(low <= high) {
			mid = (low + high) / 2;
			
			if(key == arr[mid]) {
				return mid; // 원하는 값 위치 반환
			} else if(key < arr[mid]) {
				return binarySearch1(key ,low, mid-1); // 왼쪽 부분 탐색 
			} else {
				return binarySearch1(key, mid+1, high); // 오른쪽 부분 탐색 
			}
		}
		
		return -1; // 원하는 값 없음
	}