문제
임의의 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>
내가 짱이다 😎 매일 조금씩 성장하기🌱
9/14
이분검색의 코드 논리 외우기