[Algorithm Champions] Week 6, No.12

문제

---

풀이

• 중복이 없고, 정렬된 숫자 배열에서 인덱스와 해당 값이 일치할 때 가장 작은 인덱스를 반환하는 문제다.

• 선형탐색
  - 이미 정렬되어 있으니, 맨 처음부터 해당 값과 인덱스가 같은지 비교하고, 같다면 바로 해당 인덱스를 반환한다.
  

• 이분탐색

  • 중간부터 탐색하는데, 중간값과 인덱스가 일치하는데 이전 값은 같지 않다면 중간값이 가장 작은 인덱스가 된다.
    ex) [-5, -3, 0, 3, 4, 5, 9]
    여기서 3과 idx 3이 같은지 본다. => 같다.
    그러면 이전 값인 0과 idx 2가 같은지 본다 => 다르다.
    그럼 이전값은 idx와 2만큼 차이나기 때문에 그만큼 이전 인덱스에 있는 값들이 모조리 밀리면서 인덱스과 값이 일치하는 경우가 없다.
  • 중간값과 인덱스와 비교할 때 인덱스가 더 큰 경우, 중간값의 오른쪽 부분만 보면 된다.
    -> left를 mid+1로 변경한다.
  • 중간값과 인덱스를 비교할 때 값이 더 큰 경우, 중간값의 왼쪽 부분만 보면 된다.
    -> right를 mid-1로 변경한다.

---

코드

package com.company.w6;

/*
date: 21.07.19

I: int array -> sorted, distinct int
O: int -> min idx
C: int의 범위는 없는듯 하다.
E: 해당되는 인덱스가 없을 경우 -1 반환, 입력 배열의 길이가 0일 때도 -1 반환

linear: time - O(N), space - O(1)
binary search: time - O(logN), space - O(1)
 */
public class No12 {
    public static void main(String[] args) {
        int[] array = {-5, -3, 2, 3, 4, 5, 9};
        System.out.println("linear = " + linearFindSameIdx(array));
        System.out.println("binary = " + binarySearchFindSameIdx(array));
    }

    public static int linearFindSameIdx(int[] array) {
        // base case
        if (array.length == 0) return -1;

        int minIdx = -1;
        for (int i = 0; i < array.length; i++) {
            if (array[i] == i) {
                minIdx = i;
                break;
            }
        }
        return minIdx;
    }

    public static int binarySearchFindSameIdx(int[] array) {
        // base case
        if (array.length == 0) return -1;

        int minIdx = -1;
        int left = 0, right = array.length - 1, mid;

        while (left <= right) {
            mid = left + (right - left) / 2;

            // 바로 답인 경우
            if (array[mid] == mid && array[mid - 1] != mid - 1) {
                minIdx = mid;
                break;
            }

            if (array[mid] < mid) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return minIdx;
    }
}