algorithm - 이분 검색

이분 검색 알고리즘

이분 검색 알고리즘은 일반 순차적 검색 알고리즘보다 시간복잡도가 낮아서 매율 효율적인 알고리즘이다.

사용법

1.일단 배열이 오름차순으로 정렬되어야한다.
2.배열의 중간값(mid)을 구해서 찾으려고 하는 target값보다 큰지 작은지 여부에따라서 투포인터 lt,rt의 값을 이동시키면서 값을 찾아가면된다.
3.찾아가다가 mid값이 target값과 일치하면 해당 위치는 배열 인덱스보다 +1 이기 때문에 +1을 해서 리턴해준다.

구현

public class ex8 {
    public static int solution(int n,int m,int[] arr){
        int answer=0;
        int lt=0,rt=arr.length-1;
        Arrays.sort(arr);
        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) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] arr =new int[n];
        for(int i=0; i<n; i++){
            arr[i]=sc.nextInt();
        }

        System.out.println(solution(n,m,arr));
    }
}

lt와 rt를 선언할 때는 배열의 인덱스와 값을 맞추는게 좋다.