Find Low or High Index

설명

정수형의 소트 된 배열과, 지정된 요소(key)가 위치하는 가장 낮은 인덱스(low index)와 높은 인덱스(high index)를 돌려준다. 만약, 지정된 요소가 그 배열에 없는 경우는 -1 을 돌려줍니다. 배열의 길이는 수백만 단위로 많은 중복 요소를 허용합니다.

예

다음 예제에서 low index와 high index는 다음과 같습니다.

키 : 1 low = 0 및 high = 0

키 : 2 low = 1 및 high = 1

키 : 5 low = 2 및 high = 9

키 : 20 low = 10 및 high = 10

팁

이진 검색

해설

Runtime Complexity

Binary Search를 사용하기 때문에 실행 시간은 O(logn)입니다.

Memory Complexity

상수의 O(1)입니다. 추가 메모리는 사용하지 않습니다. 그러나 Binary Search가 재귀 적으로 구현되면,
함수 호출에 의한 스택에서 암시적으로 O(logn), 메모리가 사용된다는 점에 유의하십시오.
그러나 여기서는 반복(Iteration)에 중점을 둡니다.

생각

배열 크기는 수백만 단위이므로 정렬된 배열을 low index 및 high index로 O(n)
선형 스캔은 매우 비효율적입니다. 대신 조금 수정하고 Binary Search를 사용하여
특정 키의 low index와 high index를 찾습니다.

low index를 찾는 알고리즘을 살펴 보겠습니다.

모든 단계에서 low index와 high index 사이의 배열을 고려합니다. 또한 low index와 high index의 중간 mid index를 계산합니다.

mid 의 요소가 key 이상인 경우는, high = mid - 1 이 됩니다. 만약, mid 의 요소가 key 와 같은 경우라도, 그 index 가 최저의 index 로는 한정되지 않는 것에 주의합니다.

mid 의 요소가 key 보다 작은 경우, 배열은 오름차순이므로 key 는 최초의 0 으로부터 mid 까지의 범위에 존재하지 않습니다. 따라서 mid + 1 이후에있을 수 있습니다. low = mid + 1입니다.

low 가 high 보다 큰 경우, 반복을 종료해, low 는 key 의 최초의 출현을 가리킵니다. low 요소가 key와 일치하지 않으면 -1을 반환합니다.

　*high index 를 찾아내는 경우도 상기의 프로세스와 거의 같습니다. 아래에 구현 코드가 있습니다.

구현

findLowHigh.java

import java.util.List;

public class findLowHigh{

    public int binary_search(List<Integer> arr, int low, int high, int key, boolean search_low){

        while(low <= high) {
            int mid = low + (high - low) / 2;

            if (search_low) {
                if (arr.get(mid) >= key) { // Search the left half for the next
                    high = mid - 1;
                }
                else { // Search the right half for the next
                    low = mid + 1;
                }
            }
            else {
                if (arr.get(mid) <= key) { // Search the left half for the next
                    low = mid + 1;
                }
                else { // Search the right half for the next
                    high = mid - 1;
                }
            }
        }

        if (search_low) {
            if (low == - 1) {
                return low;
            }
            else if (low < arr.size() && arr.get(low) == key) {
                return low;
            }
        } else {
            if (high == -1) {
                return high;
            }
            else if (high < arr.size() && arr.get(high) == key) {
                return high;
            }
        }

        return -1;
    }

    public int find_low_index(List<Integer> arr, int key) {
        return binary_search(arr, 0, arr.size() - 1, key, true);
    }

    public int find_high_index(List<Integer> arr, int key) {
        return binary_search(arr, 0, arr.size() - 1, key, false);
    }
}

Main.java

import java.util.Arrays;
import java.util.List;

public class Main {

    public static void main(String[] args) {

        findLowHigh algorithm = new findLowHigh();

        List<Integer> array = Arrays.asList(1,1,1,2,2,2,2,2,3,3,3,4,4,4,4,5,5,5,6,6,6,6,6,6);
        int key = 5;
        int low = algorithm.find_low_index(array, key);
        int high = algorithm.find_high_index(array, key);
        System.out.println("LowIndex of " + key + " : "+low);
        System.out.println("HighIndex of " + key + " : "+high);

        key = -2;
        low = algorithm.find_low_index(array, key);
        high = algorithm.find_high_index(array, key);
        System.out.println("LowIndex of " + key + " : "+low);
        System.out.println("HighIndex of " + key + " : "+high);
    }
}

Output