정렬된 수에서 하나의 수의 위치 찾기(이진 탐색)

정렬된 수에서 하나의 수의 위치 찾기(이진 탐색)

💡 학습 목표
    1. 문제 정의
    2. 해결 방법
    3. 연습 문제
    4. 풀이

1. 문제 정의

• 여러 개의 수가 정렬된 순서로 있을 때 특정한 수를 찾는 방법
• 단순 반복문을 이용하면 수의 개수에 따라 비교 횟수가 증가하는 O(n)의 수행이 이루어짐
• 수가 정렬된 상태에서는 이진 탐색(binary search)을 활용하면 매번 비교되는 요소의 수가 절반으로 감소될 수 있으므로 O(logN)의 수행으로 원하는 수를 찾을 수 있음
• 수의 예 : [12, 25, 31, 48, 54, 66, 70, 83, 95, 108]
• 83의 위치를 찾아보세요
• 88의 위치를 찾아보세요

2. 해결 방법

• 수가 정렬된 상태이므로 중간의 값을 하나 선택한다. 찾으려는 값이 그보다 크면 범위를 오른쪽으로 그보다 작으면 범위를 왼쪽으로 좁힐수 있다.
• 한번 비교 할때 마다 1/2씩 범위가 좁혀진다.

3. 연습 문제

public class BinarySearch {

	public static void main(String[] args) {

		// 정렬되어 있는 데이터 상태
		int[] numbers = { 12, 25, 31, 48, 54, 66, 70, 83, 95, 108 };
		int target = 83;

		// 이진 탐색을 하기 위해 필요한 초기값을 설정 하시오 
		int left; 
		int right; 
		int mid; 
		int temp;
		
		boolean find = false;
		
		// 코드를 구현 
		
		// 결과 
		// System.out.println("찾는 수는 " + mid + "번째 있습니다.");
		// 또는 
		// System.out.println("찾는 수가 없습니다.");
	}

}

4. 풀이

package useful;

public class BinarySearch {

	public static void main(String[] args) {

		// 정렬되어 있는 데이터 상태
		int[] numbers = { 12, 25, 31, 48, 54, 66, 70, 83, 95, 108};
		int target = 84;

		// 이진 탐색을 하기 위해 필요한 초기값을 설정 하시오
		int left;
		int right;
		int mid;
		int temp;

		boolean find = false;

		// 코드를 구현
		left = 0;
		right = numbers.length - 1;
		while (!find) {
			mid = (right + left) / 2;
			if (target == numbers[mid]) {
				System.out.println("찾는 수는 인덱스 " + mid + "번째에 있습니다.");
				find = true;
			} else if (target < numbers[mid]) {
				right = mid - 1;
			} else if (target > numbers[mid]) {
				left = mid + 1;
			} 
			if (right < left) {
				System.out.println("찾는 수가 없습니다.");
				find = true;
			}
			
		}
		// 결과
		// System.out.println("찾는 수는 " + mid + "번째 있습니다.");
		// 또는
		// System.out.println("찾는 수가 없습니다.");
	}

}

 

핵심 아이디어

• 반으로 가른 후 한번 비교 → 반쪽을 버리고 배열의 범위를 재정의함
• 이때 반으로 가른 인덱스의 값은 비교를 했기때문에 그 인덱스를 기준으로 ±1
• 종료 시점은 배열의 범위가 음수가 될때
• 처음에는 0이 될때도 생각 해보았지만 target 을 찾는 시점이 반복을 시작할 때고 배열의 범위가 좁혀지는 시점은 target을 찾지 못했을 때이기 때문에 다음번 반복에서 타겟을 찾는 행위를 한번 더 해야함

 

Java 유용한 클래스 - 3 으로 돌아가기