IT모아

이분 검색 본문

알고리즘

이분 검색

아롱사태남 2016.04.02 21:19

이분 검색이란 


이분검색(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;

}

}


}



'알고리즘' 카테고리의 다른 글

자바 퀵 정렬  (0) 2017.11.22
이분 검색  (0) 2016.04.02
마방진(홀수 계산식)  (0) 2016.04.02
0 Comments
댓글쓰기 폼