[이진 탐색] Binary Search Algorithm

 

오름차순 정렬이 필수인 알고리즘이다. 

 

 

특정한 값의 위치를 찾으려 할 때, 중간값을 선택하고 찾고자 하는 값의 크고 작음을 비교한다. 

 

O(log n) 의 시간복잡도를 가진다. 

 

하지만 최악의 경우에는 한쪽으로 편향된 트리가 될 수 있다. 이러한 케이스에는  시간복잡도가 O(n) 이 된다.

 

 

  public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = Integer.parseInt(sc.next());
        int m = Integer.parseInt(sc.next());

        int[] array = new int[n];
        for (int i=0; i< n; i++) {
            array[i] = Integer.parseInt(sc.next());
        }

        Arrays.sort(array);
        int answer = 0;

        int lt=0, rt =n-1;

        // 검색 타겟보다 큰값인지 작은 값인지
        // 계속 서치해나감
        while (lt<=rt) {
            int mid=(lt + rt) / 2;
            if (array[mid]==m) {
                answer = mid+1; // 정답의 index 는 0이 아닌 1부터 시작하니까.
                break;
            }
            if (array[mid]>m) {
                rt=mid-1;
            } else {
                lt=mid+1;
            }
        }

        System.out.println(answer);

    }

 

 

아래 이미지는 이분검색 알고리즘을 통해 서치한 결과이다.

 

5번 케이스는 10000개의 숫자 리스트 중에  "941"을 찾는 문제였다. 

만개의 숫자중에 941을 찾아서 인덱스가 몇번째인지를 확인한다고 하면. 오히려 소요 시간이 더 늘어난다

( 아주 미묘한 차이지만 )

리스트가 많아지고, 찾으려하는 인덱스가 최악의 상황이라면  시간복잡도 O(n)과  별반 차이가 없게 될 것이다. 

 

 

위의 속도가 더 빠른 문제 풀이는 아래와 같은 코드를 사용했다.

 

-->

 

특정 케이스에서 운좋게 찾아 낼 경우에만 빠르다는 것이다. 당연히 이분탐색의 시간 복잡도가 더 나은 방식이다. 

 

 

 

선형 탐색을 중간값부터 좌 - 우로 쏟음. 

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = Integer.parseInt(sc.next());
        int m = Integer.parseInt(sc.next());

        int[] array = new int[n];
        for (int i=0; i< n; i++) {
            array[i] = Integer.parseInt(sc.next());
        }

        Arrays.sort(array);
        int answer = 0;
        int lt =(n/2)-1, rt =n/2;
        while (true) {

            if (array[lt] == m ) {
                answer= lt;
                break;
            }

            if (array[rt] ==m ) {
                answer = rt;
                break;
            }

            lt-=1;
            rt+=1;
        }
        System.out.println(answer+1);
    }