이원 탐색 (BinarySearch) - 자바(JAVA)

c++ 언어로 작성된 수도코드를 자바로 변환한 코드입니다.

// 이미 정렬된 배열 a[0]...a[n-1]에서 x = a[j]인 j를 반환
// left, right: 탐색하고자 하는 리스트의 왼쪽, 오른쪽 끝
// 초기값으로 left = 0, right = n-1
// 리스트의 중간 위치 middle = (left + right) / 2로 설정
// a[middle]과 x 비교

// int BinarySearch (int *a, const int x, const int n)
int binarySearch(int[] a, final int x, final int n) {
    // Search the sorted array a[0],...,a[n-1] for x
    int left = 0, right = n-1;
    while (left <= right) { // there are more elements
        int middle = (left + right) / 2;
        if (x < a[middle]) right = middle - 1;
        else if (x > a[middle]) left = middle + 1;
        else return middle;
    } // end of while
    return -1; // not found
}

 

순환 알고리즘을 사용하여 이원 탐색을 하는 방법입니다.

// 순환 알고리즘: 수행이 완료되기 전에 자기 자신을 다시 호출
/* 직접 순환(direct recursion)
    함수가 그 수행이 완료되기 전에 자기 자신을 다시 호출 */
/* 간접 순환(indirect recursion)
    호출 함수를 다시 호출하게 되어 있는 다른 함수를 호출 */

int binarySearch(int[] a, final int x, final int left, final int right) {
    // 정렬된 배열 a[left],...,a[right]에서 x 탐색
    if (left <= right) {
        int middle = (left + right) / 2;
        if (x < a[middle]) return binarySearch(a, x, left, middle - 1);
        else if (x > a[middle]) return binarySearch(a, x, middle + 1, right);
        return middle;
    } // if의 끝

    return -1; // 발견되지 않음
}