이진 탐색

Binary Search(이진탐색)

Binary Search(이진탐색) 정렬된 배열, 이진 트리에서 특정한 값을 찾아내는 알고리즘이다. 정렬이 전제되어 있어야 한다. 한번 비교를 거칠 때 탐색 범위가 1/2로 줄어든다. 범위의 중앙 값과 비교한다. 찾는 값이 중앙 값보다 작다면 왼쪽(그림 : 내림차순 정렬이므로 오른쪽) 1/2의 범위에서 탐색한다. 찾는 값이 중앙 값보다 크다면 오른쪽(그림 : 내림차순 정렬이므로 왼쪽) 1/2의 범위에서 탐색한다. 1번/2번 해당하는 작업을 반복한다. 찾는 값이 중앙 값이면 탐색을 종료한다. 기본 형태의 Java 코드 int BinarySearch(int dataArr[], int size, int findData) { int low = 0, high = size - 1, mid; // high가 low보..