Binary Serach_이분검색

🔵 ThingsILearned

✔️ 이분검색

이분검색: 검색할 범위를 반으로 줄여가며 찾는 검색 ⭐️⭐️⭐️ 이분검색은 정렬이 된 상태에서 시작한다. 이분검색의 시간복잡도는 O(log n)

이분검색을 할 때는
찾는 값, 시작 위치, 종료 위치를 알하야 한다.
중간 위치를 찾을 때는 (시작 위치 + 종료 위치) /2
이 중간 위치가 찾는 값과 같다면 검색 종료,
찾는 값보다 작다면 배열의 오른쪽(더 큰 쪽) 검색
찾는 값보다 크다면 배열의 왼쪽(더 작은 쪽) 검색

✅ n개의 수를 오름차순으로 정렬한 다음 m이 어디있는지 이분검색으로 구하세요.

package com.example.ct_inflean_2024.String;

import java.util.*;

class Main {
    public int solution(int n, int m, int[] input){
        int answer=0;
        Arrays.sort(input); //오름차순으로 정렬
        int start=0;
        int end= n-1;
        while(start<=end){
            int middle= (start+end)/2;
            if(m == input[middle]){
                answer= middle+1;
                break;
            }
            if(m < input[middle]){
                end= middle-1;
            }else{
                start=middle+1;
            }
        }
        return answer;
    }
    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc= new Scanner(System.in);
        int n= sc.nextInt();
        int m= sc.nextInt();
        int[] input= new int[n];
        for(int i=0; i<n; i++){
            input[i]= sc.nextInt();
        }
        System.out.println(T.solution(n, m, input));
    }
}
//⭐️input:
8 32
23 87 65 12 57 32 99 81
//⭐️output:
3

🟢

class Main {
    public int solution(int n, int m, int[] input){
        int answer=0;
        Arrays.sort(input); //오름차순으로 정렬
        int start=0;
        int end= n-1;
        int middle= (int) (start+end)/2;
        while(m != input[middle]){
            if(m < input[middle]){
                end= middle-1;
                middle= (int) (start+end)/2;
            }else{
                start=middle+1;
                middle= end;
            }
        }
        answer= middle+1;
        return answer;
    }
    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc= new Scanner(System.in);
        int n= sc.nextInt();
        int m= sc.nextInt();
        int[] input= new int[n];
        for(int i=0; i<n; i++){
            input[i]= sc.nextInt();
        }
        System.out.println(T.solution(n, m, input));

    }
}