이진 검색(binary search)

• 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘
• 이진 검색을 한 단계씩 진행할 때마다 검색 범위가 절반이 되므로 검색에 필요한 비교 횟수의 평균값은 log n 이다.
• 알고리즘의 복잡도는 O(log n) 이다.
  • 복잡도의 대소 관계 : 1 < log n < n < n log n < n^2 < n^3 < n^k < 2^n
• JAVA는 배열에서 이진 검색을 하는 java.util.Arrays 클래스의 binarySearch 메서드로 제공한다.
  • 모든 자료형 배열에서 이진 검색을 할 수 있도록 오버로딩되어 있다.
    • [검색 성공] : 넘긴 값과 일치하는 요소의 인덱스를 반환한다. 일치하는 요소가 여러 개라면 무작위의 인덱스를 반환한다.
    • [검색 실패] : 삽입 포인트를 x라고 할 때 -x - 1을 반환한다. 삽입 포인트는 검색하기 위해 넘긴 값보다 큰 요소 중 첫 번째 요소의 인덱스이다. 만약 배열의 모든 요소가 넘긴 값보다 작다면 배열의 길이를 삽입 포인트로 정한다.

//길이가 n인 배열 a에서 key와 같은 요소를 이진 검색합니다
static int binSearch(int[] a, int n, int key) {
    int low = 0;        //검색 범위의 첫 인덱스
    int high = n - 1;    //검색 범위의 끝 인덱스
    
    while (low <= high) {
        int mid = (low + high) / 2; //중간 인덱스
        if (a[mid] == key) {
            return mid;
        } else if (a[mid] < key) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    
    return -1; //검색 실패
}