이진 탐색

이진 탐색

개념과 원리

정렬된 상태의 입력 데이터에 대한 효과적인 탐색 방법이다.

• 오름차순으로 정렬되었다고 가정되었을때

탐색 방법

• 배열의 가운데 원소 A[mid]와 탐색키 x를 비교한다.
  • 탐색키 = 가운데 원소 => 탐색 성공 ( 인덱트 mid 반환 후 종료 )
  • 탐색키 < 가운데 원소 => 이진탐색 ( 원래 크기 1/2 인 왼쪽 부분배열 ) 순환 호출
  • 탐색키 > 가운데 원소 => 이진탐색 ( 원래 크기 1/2 인 오른쪽 부분배열 ) 순환 호출

*이진탐색 ( 원래 크기 1/2 인 왼쪽 부분배열 ) / 이진탐색 ( 원래 크기 1/2 인 오른쪽 부분배열 ) 

• 탐색을 반복할 때마다 대상 원소의 개수가 1/2씩 감소 한다.

 

---

분할

• 배열의 가운데 원소를 기준으로 왼쪽과 오른쪽 부분배열로 분할한다. 탐색키와 가운데 원소가 같으면 가운데 원소의 배열 인덱스를 반환 / 종료 한다.

정복

• 탐색키가 가운데 원소보다 작으면 왼쪽 부분배열을 대상으로 이진 탐색을 순환 호출한다. 크면 오른쪽 부분배열을 대상으로 이진 탐색을 순환 호출한다.

결합

• 필요 없음 ( 부분배열에 대해서 탐색 결과가 직접 반환 한다 ) 

---

특징

• 입력 배열의 데이터가 정렬된 경우에 대해서만 적용 가능하다.
• 삽입 / 삭제 연산은 부가적인 데이터 이동을 수반한다.
  • 데이터의 정렬 상태 유지를 위해서 평균 n/2 개의 데이터 이동이 발생한다.
    • 삽입 / 삭제가 빈번한 응용에서는 부적합하다.

---

 

public class BinarySearch {

	static int[] arr = {1,3,5,7,9,11,20,35,99,100};

	public static void main(String[] args) {
		System.out.println(binarySearch(99,0,arr.length-1));
		System.out.println(binarySearch2(99,0,arr.length-1));
	}
	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 binarySearch(key, low , mid-1); // 왼쪽 부분에서 탐색 하기
			} else {
				return binarySearch(key,mid+1,high); // 오른쪽 부분에서 탐색하기
			}
		}
		return -1; // 탐색 실패 시
	}
	static int binarySearch2(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;
	}
}