이분 검색

이분 검색이란 

이분검색(Binary Search)은 처음 값과 마지막 값에 대한 중간 값을 설정한 후 검색 대상이 되는 키 값과 비교해서 검색하는 검색 방법을 말한다.

자료가 많을수록 이분 검색 알고리즘은 효율적이며 색인 순차파일 등에서 색인 영역을 탐색하는데 유용하게 사용될 수 있다.

그러나 탐색을 위해서는 데이터가 정렬되어 있어야 하므로 데이터의 삽입이나 삭제가 빈번한 자료일 경우에는 비효율 적이다.

public int binarySearch(TYPE a[], int right, int left TYPE key) {

while (right >= left) {

int mid = (right + left) / 2;

if(a[mid] == key) return mid;

if(key > a[mid]) {

left = mid + 1;

} else {

right= mid -1;

}

}

}