코드트리 조별과제 5회차 (8.12 ~ 8.18)

Binary Search

 

[ 문제 ]

[4, 2, 1, 5, 7, 3] 와 같이 숫자들이 주어졌을 때, 숫자 2가 위치하는 인덱스 값을 찾는 프로그램을 작성하시오.

 

 

 

[ 해결책(1) - O(N) ]

무작정 코드를 작성한다면, 아래 코드처럼 처음부터 끝까지 O(N)만큼 해당 숫자가 나올때까지 검색 해야 할 것이다.

public class Main {
    public static void main(String[] args) {
        int n = 6, target = 2;
        int[] arr = new int[]{0, 4, 2, 1, 5, 7, 3};
 
        int idx = -1;
 
        for(int i=1; i<=n; i++){
            if(arr[i] == target) {
                idx = i;
                break;
            }
        }
 
        System.out.print(idx); // 2가 있는 인덱스인 2가 답이 됩니다.
    }
}
 

 

 

 

[ 해결책(2) - O(LogN) ]

O(logN) 방법은 업/다운 게임처럼 찾아야 하는 수의 범위를 줄이는 방법이다.

중앙(mid)부터 검색하여 찾는 target 값이 크다면 위로 검색하고 작다면 아래로 검색하는 것이다.

단, 위 조건을 성립하기 위해서는 정렬이 필요하다. 여기서 While 문을 통해 원소의 갯수가 1일 때 까지 계속 탐색하여 left와 right 변수를 사용하여 움직임으로써 해당 target 값을 찾을 수 있다. 코드는 다음과 같다.

public class Main {
    public static void main(String[] args) {
        int n = 6, target = 2;
        int[] arr = new int[]{0, 4, 2, 1, 5, 7, 3};
 
        int idx = -1;
 
        // 이진탐색을 진행합니다.
        int left = 0, right = n - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if(arr[mid] == target) { // 찾았다면 해당 index를 반환합니다.
                idx = mid;
                break;
            }
 
            if(arr[mid] > target) // 찾으려는 숫자가 더 작다면
                right = mid - 1;  // 왼쪽 구간으로 이동해야 합니다.
            else                  // 찾으려는 숫자가 더 크다면
                left = mid + 1;   // 오른쪽 구간으로 이동해야 합니다.
        }
 
        System.out.print(idx); // 2가 있는 인덱스인 2가 답이 됩니다.
    }
}
 

 

 

 

연습문제 - (코드트리) 숫자 빠르게 찾기

 

https://www.codetree.ai/missions/8/problems/find-number-fast?&utm_source=clipboard&utm_medium=text

 

 

 

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, M, arr[], ans;
 
    static StringBuilder sb = new StringBuilder();
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        arr = new int[N+1];
 
        st = new StringTokenizer(br.readLine());
        for(int i=1; i<=N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
 
        for(int i=1; i<=M; i++){
            int target = Integer.parseInt(br.readLine());
 
            solve(target);
        }
 
        System.out.print(sb);
    }
 
    static void solve(int target){
        int left = 1, right = N, idx = -1;
 
        while (left <= right) {
            int mid = (left + right) / 2;
            if(arr[mid] == target) { // 찾았다면 해당 index를 반환합니다.
                idx = mid;
                break;
            }
 
            if(arr[mid] > target) // 찾으려는 숫자가 더 작다면
                right = mid - 1;  // 왼쪽 구간으로 이동해야 합니다.
            else                  // 찾으려는 숫자가 더 크다면
                left = mid + 1;   // 오른쪽 구간으로 이동해야 합니다.
        }
 
        sb.append(idx + "\n");
    }
}