회전된 배열에서의 이진 탐색 - java

회전된 배열에서 이진 탐색으로 값 찾기 (java)

---

아래와 같은 크기 5짜리 회전된 배열이 있다고 가정해보자.

[1,2,3,4,5]

[2,3,4,5,1]

[3,4,5,1,2]

[4,5,1,2,3]

[5,1,2,3,4]

이진탐색은 우선 mid = (start+end)/2 인덱스, 해당 배열의 가운데부터 탐색을 시작한다.

찾으려는 값이 mid와 다를 경우, 크게 두가지 경우의 수로 나누어 생각한다.

1. mid 까지 정렬된 경우

2. mid 까지 정렬 안된 경우

---

1. mid까지 정렬된 경우

[1,2,3,4,5]

[2,3,4,5,1]

[3,4,5,1,2]

위의 3가지 경우가 해당된다.

이런 경우 또 2가지의 경우로 나누어 생각한다.

1.1 - 찾고자 하는 값이 start ~ mid 사이에 있는 경우
1.2 - 1.1이 아닌경우

1.1의 경우에 속하면 start, (mid-1)의 범위로 이진 탐색을 실시, 1.2 의 경우에는 (mid+1), end의 범위로 이진 탐색을 실시한다.

---

2. mid 까지 정렬이 안되어있는 경우

[4,5,1,2,3]

[5,1,2,3,4]

위의 2가지 경우가 해당된다.

이 경우 마찬가지로 2가지 경우로 나누어 생각한다.

(mid까지 정렬이 안되어있다는 얘기는 반대로 말하면 mid에서 end까지는 정렬이 되어있다는 얘기가 된다.)

2.1 - 찾고자 하는 값이 mid ~ end 사이에 있는 경우
2.2 - 2.1이 아닌 경우

2.1의 경우에 속하면 (mid+1), end의 범위로 이진 탐색을 실시, 2.2의 경우에는 start, (mid-1)의 범위로 이진 탐색을 실시한다.

---

        {
            int[] arr = new int[]{1, 2, 3, 4, 5};

            int idx = findIndexRotatedArray(arr, 0, arr.length - 1, 3);
            assert (2 == idx);

            arr = new int[]{2, 3, 4, 5, 1};

            idx = findIndexRotatedArray(arr, 0, arr.length - 1, 3);
            assert (1 == idx);

            arr = new int[]{3, 4, 5, 1, 2};

            idx = findIndexRotatedArray(arr, 0, arr.length - 1, 3);
            assert (0 == idx);

            arr = new int[]{4, 5, 1, 2, 3};

            idx = findIndexRotatedArray(arr, 0, arr.length - 1, 3);
            assert (4 == idx);

            arr = new int[]{5, 1, 2, 3, 4};

            idx = findIndexRotatedArray(arr, 0, arr.length - 1, 3);
            assert (3 == idx);
        }

    public static int findIndexRotatedArray(int[] arr, int start, int end, int data) {
        if (end < start) {
            return -1;
        }

        int mid = (start + end) / 2;
        if (arr[mid] == data) {
            return mid;
        }

        if (arr[start] <= arr[mid]) {
            if (arr[start] <= data && data <= arr[mid]) {
                return findIndexRotatedArray(arr, start, mid - 1, data);
            }

            return findIndexRotatedArray(arr, mid + 1, end, data);
        }

        if (arr[mid] <= data && data <= arr[end]) {
            return findIndexRotatedArray(arr, mid + 1, end, data);
        }

        return findIndexRotatedArray(arr, start, mid - 1, data);
    }

---

출처 - POCU 아카데미 COMP3500 강의