7-10) 이분검색

7706 단어 이분탐색이분검색이분검색

문제

임의의 N개의 숫자가 입력으로 주어집니다. N개의 수를 오름차순으로 정렬한 다음 N개의 수 중 한 개의 수인 M이 주어지면 이분검색으로 M이 정렬된 상태에서 몇 번째에 있는지 구하는 프로그램을 작성하세요. 단 중복값은 존재하지 않습니다.
[입력설명]
첫 줄에 한 줄에 자연수 N(3<=N<=1,000,000)과 M이 주어집니다. 두 번째 줄에 N개의 수가 공백을 사이에 두고 주어집니다.
[출력설명]
첫 줄에 정렬 후 M의 값의 위치 번호를 출력한다.

입력예제 1

8 32
23 87 65 12 57 32 99 81

출력예제 1

3

문제 풀이

예습 이론

  • 이분검색(이분탐색)은 시간복잡도가 O(n)이다.
    우선 이분검색을 하기 위해서는 자료가 정렬 되어있어야한다. 한번 비교할때마다 자료의 절반이 줄기 때문에, 시간복잡도가 낮다.
    보통 포인터 3개를 사용하며, lt는 left pointer, rt는 right pointer, mid=(lt+rt)/2로 사용된다.

  • parseInt((lt+rt)/2)는 소수점을 삭제한다

코드

<html>
    <head>
        <meta charset="UTF-8">
        <title>출력결과</title>
    </head>
    <body>
        <script>
            function solution(target, arr){
                let answer;
                arr.sort((a, b)=>a-b); //오름차순 정렬
                let lt=0, rt=arr.length-1;
                while(lt<=rt){
                    let mid=parseInt((lt+rt)/2);
                    if(arr[mid]===target){
                        answer=mid+1; //인덱스는 0부터 시작하니까 +1해줌
                        break;
                    }
                    else if(arr[mid]>target) rt=mid-1;
                    else lt=mid+1; //arr[mid]<target일 때
                }
                return answer;
            }

            let arr=[23, 87, 65, 12, 57, 32, 99, 81];
            console.log(solution(32, arr));
        </script>
    </body> 
</html>
Chapter 11 기본 클래스
이벤트 버블링(Event Bubbling), 이벤트 캡쳐(Event Capture)

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage