문제.
임의의 N개의 숫자를 입력하고 오름차순으로 정렬한 다음 N개의 수 중 한 개의 수인 M이 주어지면
이분검색으로 M이 정렬된 상태에서 몇 번째에 있는지 구하는 프로그램을 작성하시오. 단 중복값은 존재하지 않는다.
입력 예시
8 32
23 87 65 12 57 32 99 81
답 : 3
나의 답변
public class Main {
public int solution(int n, int m, int[] arr) {
int answer=0;
// 오름차순으로 정렬
Arrays.sort(arr);
// 처음과 끝을 가리키는 두 포인터 설정
int lt=0;
int rt=arr.length-1;
// 처음과 끝 포인터가 같기까지 while문 반복
while(lt<=rt) {
// 중간값
int midIdx=(lt+rt)/2;
// 중간값과 찾고자하는 값이 같을 시
if(arr[midIdx]==m) {
// 몇번째인지이므로 1부터 시작 따라서 인덱스보다 +1
answer=midIdx+1;
break;
}
else {
// 중간값보다 작을시
if(arr[midIdx]>m) {
// 끝포인터를 중간값 인덱스-1
rt=midIdx-1;
}else {
// 시작포인터를 중간값 인덱스+1
lt=midIdx+1;
}
}
}
return answer;
}
public static void main(String[] args) {
Main T = new Main();
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(T.solution(n, m, arr));
}
}
이분 검색 동작
이분 검색은 배열이나 리스트가 이미 정렬되어 있어야 한다.
- 배열 또는 리스트의 중간 값을 선택한다.
- 처음과 끝을 가리키는 두 포인터를 사용해 중간 값이 인덱스를 찾는다.
- 중간 값( (시작포인터 + 끝포인터) / 2)과 찾고자하는 값과 비교한다.
- 찾고자하는 값이 중간 값보다 작다면 시작포인터 동일, 끝 포인터 : 중간 값 인덱스 -1
- 찾고자하는 값이 중간 값보다 크다면 시작포인터 : 중간 값 인덱스+1, 끝 포인터 동일
- 위 과정을 반복한다.
이분 검색과 이진 탐색 트리의 공통점
- 탐색 수행 시 범위를 반으로 줄여나감
- 시간복잡도 O(log n)
이분 검색과 이진 탐색 트리의 차이점
- 이분 검색
- 주로 배열 또는 리스트에서 동작
- 데이터 추가나 삭제가 어렵고 오로지 검색을 위한 구조
- 이진 탐색 트리
- 각 노드가 0~2개의 자식을 가지는 트리 구조에서 동작
- 데이터 추가, 삭제, 검색 모두 어렵지않게 수행