이분 검색

이분 검색 = Binary Search

정렬 된 데이터 집합을 가지고 수행해야 한다.

자세한 정보 : https://prosto.tistory.com/165

요약

정렬(오름차순) 된 데이터 집합을 반으로 쪼개어 2분할 한 다음,

찾아야 하는 값이 m 이고, 반으로 쪼갠 기준이 된 값을 mid 라고 했을 때

mid > m 이면 왼쪽 구간을 탐색
mid < m 이면 오른쪽 구간을 탐색한다.

탐색 방법은
처음과 같이 데이터 집합을 반으로 쪼개어
mid 가 m 보다 큰지 작은지 판단 후 분할을 반복하거나,
mid 가 m 과 같다면 반환한다.

코드

데이터 집합에서 이분 검색으로 m 찾기

public int 이분검색(int n, int m, int[] arr) {

    Arrays.sort(arr);

    int lt = 0, rt = n - 1;
    
    while (lt <= rt) {
        int mid = (lt + rt) / 2;

        if (arr[mid] == m)
            return mid;

        if (arr[mid] > m)
            rt = mid - 1;
        else
            lt = mid + 1;
    }

    return -1;
}