Binary Search Algorism & Flowchart

Binary Search Algorism & Flowchart

Binary Search는 제어 검색에서 가장 대표적인 방법으로 데이터가 크기순서대로 정렬되어 있는 상태에서 어떤 항목을 빠르게 찾기 위한 알고리즘이며 데이터가 정렬되어 있어야 한다는 전제조건을 가진다. 즉, 이진검색은 버블소트처럼 리스트의 앞에서부터 순차적으로 비교검색이 되는 것이 아닌 전체데이터의 개수가 n개일때 n/2번째의 데이터를 기준으로 전체데이터를 두 개의 서브파일로 나눈후 리스트의 한가운데에 위치해 있는 항목과 비교된다. 그런 다음 가운데에 있는 값과의 비교 결과에 따라 다음 순서가 결정된다. 그 처음 비교결과후의 동작은 세가지로 구분되는데

①찾고자 하는 값이 비교대상보다 작은 경우

②찾고자 하는 값이 비교대상과 같은 경우

③찾고자 하는 값이 비교대상보다 큰 경우

로 구분된다.

①찾고자 하는 값이 비교대상보다 작은 경우에는 찾고자 하는 값이 0번째부터 처음 비교한 (n/2)-1의 범위에 존재함으로 축소된 검색범위에 대해 동일한 과정을 되풀이 하여 수행된다.

②찾고자 하는 값이 비교대상과 같은 경우에는 찾고자 하는 값이 발견되었으므로 검색은 종료된다.

③찾고자 하는 값이 비교대상보다 큰 경우에는 찾고자 하는 값이 (n/2)+1에서 n의 범위내에 존재함으로 축소된 검색범위에 대해 ①번과 같이 동일한 과정을 되풀이하여 수행된다.

이진검색은 검색을 한번 수행할 때마다 검색범위가 1/2씩 줄어가므로 많은 자료에서 검색할 때 효율이 높다고 할 수 있으며 최악의 경우라도 평균비교횟수보다 한번 더 많을 뿐이다.

Binary Search의 소스코드 예 class ArrayTests { public void main(String []args) { int [] a = {1,3,5,7,9}; for(int I = 0; i <= 10; i++) { testValue(a, i); } } private void testValue(int [] values, int value) { int index = Arrays.binarySearch(values, value); String msg = "value[=" + value + "] index is "; System.out.print(msg + index); System.out.print(", LE[=" + getLessEqualIndex(index) + "]"); System.out.print(", LE[=" + getGreatEqualIndex(index) + "]"); System.out.println(); } pricate int getLessEqualIndex(int index) { return (Math.abs(index * 10 + 5) - 5 ) / 10; } private int getGreatEqualIndex(int index) { return Math.abs(index + 1); } }

flowchart (플로우차트)

또다른 플로우차트