🥗 이분검색

🥙 문제

🥙 풀이

🍥 순차검색 vs 이분검색

• 순차검색을 할 경우 O(N)의 시간 복잡도를 갖는다.

🍥 1단계

• 이분 검색을 하기 위해서는 정렬을 해야 한다.!
  입력값이 위와 같이

8 32
23 87 65 12 57 32 99 81

일 경우에 아래와 같이 오름차순으로 정렬해 준다.

🍥 2단계

• mid의 값을 설정 (lt + rt) / 2 로 둔다.
• arr[mid] == m 이면 answer = mid+1 이 된다.

첫 번째 경우

• arr[mid] 의 값과 입력값 32 의 크기를 비교 한 후, arr[mid] > 입력값 이면, arr[mid] ~ arr[rt] 까지의 값들은 비교를 할 필요가 없어 지게 된다.
• rt == mid-1 로 설정하고 위와 같은 방법을 반복한다.

두 번째 경우

• arr[mid] 의 값과 입력값 32 의 크기를 비교 한 후, arr[mid] < 입력값 이면, arr[lt] ~ arr[mid] 까지의 값들은 비교를 할 필요가 없어 지게 된다.
• lt == mid+1 로 설정하고 위와 같은 방법을 반복한다.

🥙 소스코드

package algolecture;

import java.util.Arrays;
import java.util.Scanner;

public class Main50 {

    public int solution(int n, int m , int[] arr){

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

        // 이분검색은 외우자!!
        int lt = 0, rt = n-1;
        while(lt <= rt){
            int mid = (lt+rt) /2;
            if(arr[mid] == m){
                answer = mid+1;
                break;
            }
            if(arr[mid] > m)
                rt = mid-1;
            else
                lt = mid+1;
        }
        return answer;
    }
    public static void main(String[] args) {
        Main50 T = new Main50();
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        int m = kb.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++)
            arr[i] = kb.nextInt();
        System.out.println(T.solution(n, m, arr));


    }

}