Binary Search

일반적인 Binary Search

오름차순으로 정렬되어 있는 배열에서 찾고 싶은 값의 IDX를 찾는 것이 목적.

public int binarySearch(int[] arr, int target){
    int s = 0;
    int e = arr.length;
    while (s < e) {
        int mid = (s + e) / 2;
        if(arr[mid] == target) return mid;
        else if (arr[mid] > target) e = mid - 1;
        else s = mid + 1;
    }
    return -1;
}

LowerBound

오름차순으로 정렬되어 있는 배열에서 한 값이 삽입 될 수 있는 위치중에서 가장 오른쪽의 IDX를 반환한다.

• Target보다 크거나 같은 값 중에서 가장 오른쪽에 있는 값

public int lowerBound(int[] arr, int target) {
    int s = 0;
    int e = arr.length;
    while (s < e) {
        int mid = (s + e) / 2;
        if (arr[mid] >= target) e = mid; // 크거나 같은 값이 필요하기 때문에 target보다 크거나 같은 값을 포함하여 다시 탐색.
        else s = mid + 1;
    }
    return s;
}

UpperBound

오름차순으로 정렬되어 있는 배열에서 한 값이 삽입 될 수 있는 위치중에서 가장 왼쪽의 IDX를 반환한다.

• Target보다 큰 값중에서 가장 왼쪽에 있는 값

public int upperBound(int[] arr, int target) {
    int s = 0;
    int e = arr.length;
    while (s < e) {
        int mid = (s + e) / 2;
        if (arr[mid] > target) e = mid; // 확실하게 큰 값만 필요하기 때문에 target과 같은 값은 제외하여 탐색.
        else s = mid + 1;
    }
    return s;
}