<java> 이분탐색 사용

이분 탐색

이분탐색 원리 오른차순 또는 내림차순으로 정렬된 배열에 적용 가능한 탐색 기법

정렬된 배열에서 특정 값을 찾을때 정 중앙에 위치한 값을 활용하면 빠른 속도로 탐색을 끝낼수 있다.

 

 

 

이분 탐색 알고리즘

• 시간복잡도: O(logN)
• 반복문과 재귀 두 가지 방법을 사용할 수 있다.

1. 자료를 오름차순으로 정렬한다.
2. 자료의 중간값(mid)이 찾고자 하는 값(target)인지 비교한다.
3. mid 값이 target과 다르다면 대소관계를 비교하여 탐색 범위를 좁히고, target과 mid 값이 같을 때까지 아래 조건에 따라 2번과 3번을 반복한다.

          ⓐ target이 mid 값 보다 작으면 end를 mid 왼쪽 값으로 바꿔준다. (절반의 왼쪽 탐색)

          ⓑ target이 mid 값 보다 크면 start를 mid 오른쪽 값으로 바꿔준다. (절반의 오른쪽 탐색)

 

 

lowerboound

찾고자 하는 값 이상이 처음 나타나는 위치

public int lowerBound(int[] arr, int target) {
    int left = 0, right = arr.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

 

upperbound

찾고자 하는 값 보다 큰 값이 처음으로 나타나는 위치(초과)

public int upperBound(int[] arr, int target) {
    int left = 0, right = arr.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

 

 

추가!!

upper bound와 lower bound는 이상, 초과 값을 구하는 방식이다.

그럼 이하, 미만은 어떻게 구할까?

 

본인을 포함하며 자신보다 작은 값의 idx는 upperbound -1 의 idx 값을 가진다.

public int upperBoundModified(int[] arr, int target) {
    int left = 0, right = arr.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left - 1; // target 값과 같거나 작은 가장 큰 인덱스
}

 

이런 방식으로 미만 또한 lowerbound 의 -1 idx를 가질 것이다.