본문 바로가기
코딩테스트 및 알고리즘

이분 검색

by 영카이브 2024. 2. 15.

문제.

임의의 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));
	}
}

 

 

 


이분 검색 동작

 

이분 검색은 배열이나 리스트가 이미 정렬되어 있어야  한다.

  1. 배열 또는 리스트의 중간 값을 선택한다.
  2. 처음과 끝을 가리키는 두 포인터를 사용해 중간 값이 인덱스를 찾는다.
  3. 중간 값( (시작포인터 + 끝포인터) / 2)과 찾고자하는 값과 비교한다.
  4. 찾고자하는 값이 중간 값보다 작다면 시작포인터 동일, 끝 포인터 : 중간 값 인덱스 -1
  5. 찾고자하는 값이 중간 값보다 크다면 시작포인터 : 중간 값 인덱스+1, 끝 포인터 동일
  6. 위 과정을 반복한다.

 

이분 검색과 이진 탐색 트리의 공통점 

  • 탐색 수행 시 범위를 반으로 줄여나감
  • 시간복잡도 O(log n) 

 

이분 검색과 이진 탐색 트리의 차이점

  • 이분 검색
    • 주로 배열 또는 리스트에서 동작
    • 데이터 추가나 삭제가 어렵고 오로지 검색을 위한 구조 
  • 이진 탐색 트리 
    • 각 노드가 0~2개의 자식을 가지는 트리 구조에서 동작
    • 데이터 추가, 삭제, 검색 모두 어렵지않게 수행 

 

 

 

 

 

 

 

 

참고 자료 출처 : https://www.inflearn.com/course/lecture?courseSlug=%EC%9E%90%EB%B0%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%ED%85%8C%EB%8C%80%EB%B9%84&unitId=72761&category=questionDetail&tab=curriculum

'코딩테스트 및 알고리즘' 카테고리의 다른 글

결정 알고리즘 2  (0) 2024.02.18
결정 알고리즘  (0) 2024.02.16
좌표 정렬  (0) 2024.02.06
정렬 응용  (0) 2024.02.03
중복확인  (0) 2024.01.31