[알고리즘] 이진 탐색(Binary search)을 통해 수 찾기

02. 정렬된 수에서 하나의 수의 위치 찾기

---

1) 문제정의

여러개의 수가 정렬된 순서로 있을 때 특정한 수를 찾는 방법
* 83의 위치를 찾아보세요

2) 수의 예

[12, 25, 31, 48, 54, 66, 70, 83, 95, 108]

---

3) 해결

package fastCampus.arg02;

public class BinarySearchProblem {

    public static void main(String[] args) {

        int[] numbers = {12, 25, 31, 48, 54, 66, 70, 83, 95, 108};

        int target = 83; // 찾을 숫자
        //int target = 88;

        int left = 0; 
        int right = numbers.length-1; 
        int mid = (left + right)/2; 

        int temp = numbers[mid]; 
        boolean find = false; 

        while(left <= right) { 

            if(target == temp) {
                find = true;
                break; 
            } else if(target < temp) { 
                right = mid-1;    
            } else { 
                left = mid+1;
            }
            mid = (left+right)/2; 
            temp = numbers[mid];
        }

        if(find == true) {
            mid++; 
            System.out.println("찾는 수는" + mid + "번째 있습니다.");
        } else
            System.out.println("찾는 수가 없습니다.");
    }
}

4) 풀이

이 문제에서 핵심은 정렬되어있는 수들이다.

정렬된 수에서 수를 찾는 방법은 다양하지만, 그 중 이진 탐색(binary search)을 활용하면 빠른 시간내로 결과를 얻을 수 있다.

이진 탐색(binary search) :  이진 탐색 알고리즘은 정렬된 정수의 리스트를 같은 크기의 두 부분 리스트로 나누고, 필요한 부분에서만 탐색하는 방법 ex) UP & DOWN 숫자 게임

---

이진 탐색 그림으로 이해하기

1~10 사이에서 숫자 7 찾기

A는 빠른 시간내로 찾기위해서 중간 수인 5를 말한다. B는 UP이라고 대답한다.

A는 6~10 중 중간숫자 8을 말한다. B는 down이라고 대답한다..

A는 원하는 숫자 7을 찾았다.

---

여기서 중요하게 봐야할 포인트는 정렬된 수들 중에서 결과를 얻는다는 것이다.

정렬은 보통 오름차순(ASC), 내림차순(DESC) 방식으로 나뉜다.
오름차순(ASC) : 어센딩, 1, 2, 3, 4, ...
내림차순(DESC) : 디센딩, 10, 9 ,8 7, ...

12, 25, 31, 48, 54, 66, 70, 83, 95, 108

문제에서 제기된 오름차순으로 정렬된 수들을 numbers 배열 안에 넣는다.

우리가 찾을 숫자를 target이라는 변수로 만든다.

처음 임의값을 지정할 때는 배열에서 중간 위치에 숫자로 지정한다.

따라서 배열의 제일 왼쪽에 있는 숫자를 left, 제일 오른쪽에 있는 숫자를 right 변수로 지정한 후

지정 값을 mid라는 변수로 (left + right)/2를 선언해준다.

* 여기서 left, right, mid는 배열의 위치이다.
* right는 numbers.length -1 을 선언한다. 배열의 인덱스는 0부터 시작하므로 n-1 (배열의 크기가 10이라면, 맨 끝은 9에 해당)

임의값은 temp 변수이다. 위에서 말했듯이 임의값은 배열의 중간 숫자이기 때문에 numbers[mid]를 선언한다.

이제 temp와 target이 맞을 때까지 반복을 진행한다.

만약 모두 검색했는데 temp와 target이 동일하지 않다면, 찾는 숫자가 없다는 결과를 출력한다.

* target < temp : up&down 게임에서 down에 해당
 1~10 중 5를 선언했을 때 down이라면, 그 다음은 1~4 까지 중 탐색하면 됨 (mid-1)
* target > temp : up&down 게임에서 up에 해당
 1~10 중 5를 선언했을 때 up이라면, 그 다음은 6~10 까지 중 탐색하면 됨 (mid+1)