08-2 이진 검색

※ 이진 검색(Binary Search)

 - 가운데에 있는 항목을 키값과 비교하여 키값이 더크면 오른쪽을 검색하고, 키값이 더 작으면 왼쪽 부분을 검색하는 방법이다.

 - 가운데 값을 기준으로 왼쪽과 오른쪽의 두 부분으로 나누어 검색하는데 이를 이분 검색 또는 보간 검색(Interpolation Search)라고도 한다.

 - 지속적으로 왼쪽과 오른쪽으로 분할해가며 검색 범위를 반으로 줄여가면서 검색한다.

 - 분할 정복 (divide and conquer)기법이라고도 한다.

 - 이진 검색 방법은 시간 복잡도가 다른 검색 방법에 비해 좋지만, 항상 배열의 상태를 정렬된 상태로 유지해야 하므로

   삽입이나 삭제시 추가 작업이 필요할 수 있다.

BinarySearch

public class BinarySearch {

      

      public void binarySearch(int a[], int low, int high, int key){

            

            if(low>high){

                  System.out.println("해당 키값 " + key +"은 없습니다.");

                  return;

            }

            

            int middle = (low+high)/2;

            

            if(a[middle] == key){

                  System.out.println((middle+1) + "번쨰 원소에서 검색 완료");

                  return;

            }else if(a[middle]> key){

                  binarySearch(a, middle+1, high , key);

            }else if(a[middle]< key){

                  binarySearch(a, low, middle-1, key);

            }

            

            return;

      }

}

Main

public class Main {

      public static void main(String[] args) {

            int a[] = {9,8,7,6,5,4,3,2,1};

            int size = a.length;

            BinarySearch bs = new BinarySearch();

            System.out.println("\n 이진검색");

            bs.binarySearch(a, 0, size-1, 9);

            bs.binarySearch(a, 0, size-1, 6);

            bs.binarySearch(a, 0, size-1, 100);

            bs.binarySearch(a, 0, size-1, -1);

      }

}