자바 이진트리
-
[JAVA/Level2] 정렬된 수에서 하나의 수 위치 찾기Algorithm/프로그래머스 2021. 6. 11. 23:33
문제 설명 여러 개의 수가 정렬된 순서로 있을 때 특정한 수를 찾으세요. 수의 예: [12, 25, 31, 48, 54, 66, 70, 83, 95, 108] 단순 반복문을 이용하면 수의 개수에 따라 비교 횟수가 증가하는 O(n)의 수행이 이루어진다. 수가 정렬된 상태에서 이진 탐색을 활용할 경우 매번 비교되는 요소의 수가 절반으로 감소될 수 있으므로 O(logN)의 수행으로 원하는 수를 찾을 수 있다. 입출력 예 찾고자하는 수의 위치를 찾을 경우 배열 내 인덱스의 값을 출력하세요. 찾고자하는 수가 존재하지 않을 경우 "찾는 숫자가 존재하지 않습니다."를 출력하세요. 풀이 수가 정렬된 상태이므로 중간의 값을 하나 선택하고, 찾으려는 값이 그보다 크면 범위를 오른쪽으로 그보다 작으면 범위를 왼쪽으로 좁히며..