설명

임의의 N개의 숫자가 입력으로 주어집니다. N개의 수를 오름차순으로 정렬한 다음 N개의 수 중 한 개의 수인 M이 주어지면

이분검색으로 M이 정렬된 상태에서 몇 번째에 있는지 구하는 프로그램을 작성하세요. 단 중복값은 존재하지 않습니다.

코드

public class BinarySearch {
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        int input1 = in.nextInt();
        int input2 = in.nextInt();
        int[] arr = new int[input1];
        for(int i=0; i<input1; i++){
            arr[i] = in.nextInt();
        }
        int solution = solution(input2, arr);
        System.out.println(solution);
    }
    public static int solution(int target, int[] arr){
        int answer = 0;
        Arrays.sort(arr);
        //lt와 rt를 선언 lt=시작, rt는 배열의 끝
        //mid를 선언 mid는 lt+rt/2 == 배열의 중앙
        int lt=0;
        int rt = arr.length -1;
        while(lt<=rt){
            int mid = (lt+rt)/2;
            if(arr[mid]==target){
                answer = mid+1;
                break;
            }else if(arr[mid]>target){
                rt = mid-1;
            }else{
                lt = mid+1;
            }
        }

        return answer;
    }
}

이분 검색 알고리즘인데 자세한건 검색을 해보면 더 잘 나와있으니 따로 설명하지 않겠다.

그런데 이글을 올리는 이유는 대부분 이분 검색 알고리즘은 재귀적 방법으로 풀이된 곳이 많은데 이렇게 반복문의 코드로도 짤수 있는걸 저장해두고 싶어서 이기 때문이다.

이분검색에 가장 중요한 포인트는 배열이 무조건 정렬되어 있어야한다는 점이다. 무조건! 정렬되어 있지 않은 배열에서 이분 검색을 해도 결과는 리턴되지만 답은 절대로 아니다.