[이진탐색: JAVA] 무작위 수 찾기

이진탐색 이란 ? 

범위의 절반인 50을 시도해가며 탐색하는 과정을 이진탐색이라고 합니다. 

예를 들어, 100페이지인 책에서 70 페이지를 찾아가고 싶다고 가정했을 때 

순차탐색의 경우, 1부터 70 까지 하나하나 1,2,3...68,69,70 이런 식으로 찾아가게 됩니다. 

이진탐색의 경우,  100의 절반인 50을 찾은 후 타겟(70) 보다 작은 경우이기에 50~100 으로 범위를 변경하고

50~100까지의 절반인 75를 찾습니다. 그리고 타겟보다 큰 경우이기에 50~75 로 범위를 다시 변경합니다. 

이런식으로 절반씩 범위를 줄여나가는 것을 이진탐색이라합니다. 

 

이진탐색을 통해 푼 무작위 수 찾기 문제

코딩테스트 강의를 듣던 중 아래 문제를 푸는 과정을 기록하려합니다. 

무작위 숫자로 되어있는 array 에서 target 인 2가 있다면 true, 아니면 false 를 반환하는 문제 입니다.

 

처리 방식

1. 무작위인 배열을 stream 의 sorted 를 사용하여 정렬한다. 

• 이진탐색은 범위의 중간값이 target 보다 큰지, 작은지를 비교해야하기 때문에 정렬되어 있어야한다. 

 

2. 최소값과 최대값, 탐색값을 선언한다. 

• 최소값은 배열의 index 인 처음으로 선언한다.
• 최대값은 배열의 index 인 가장 마지막으로 선언한다. 
  • 여기서 최소값 최대값 을  선언한 이유는 이진탐색의 범위를 좁혀나갈 때 사용되기 때문이다. 
• 탐색값은 최소값과 최대값의 합인 절반으로 선언한다. 
  • 보통 1~100 p 까지 있을 때 딱 절반을 구하기 위해 1+100 을 하여 딱 절반을 구하기 때문이다. 
  • 또한 탐색값이 있어야 target 보다 큰지, 작은지를 판단하여 범위를 좁혀나가기 때문이다. 

3. min 이 max 보다 작거나 같을 때 까지만 반복문을 돌리며 범위를 좁혀나간다. 

4. 그 후 이진탐색의 방식으로 target 이 탐색값 보다 큰지 작은지를 비교하여 target 이 존재하는지 확인한다. 

 

public class FindingTarget {

    public static void main(String[] args) {
        int target = 2;
        int[] array = {0, 3, 5, 6, 1, 2, 4};
        System.out.println(isExistTargetNumberBinaryProblem(target, array));
    }
    
    private static boolean isExistTargetNumberBinaryProblem(int target, int[] arr) {
    
    	// 이진탐색 특징 : 정렬된 배열에서만 가능함
        int[] array = Arrays.stream(arr).sorted().toArray();

        int min = 0;
        int max = arr.length - 1;
        int existingNum = (min + max) / 2; // 탐색값 인덱스 

        while(min <= max) {
            if(arr[existingNum] == target) {
                return true;
            } else if(arr[existingNum] < target) {
                // 최소를 탐색값 보다 큰 값으로 대입
                min = existingNum + 1;
            } else { // arr[existingNum] > target
                // 최대를 탐색값 보다 작은 값으로 대입
                max = existingNum - 1;
            }

            existingNum = (min + max) / 2;
        }

        return false;
    }
 }

 

 

 

 

 

 

참고 : 38군데 합격 비법, 2024 코딩테스트 필수 알고리즘