이진(이분)탐색(Binary Search)

이진 탐색이란?

이진(Binary) 라는 뜻은 0,1이라는 것을 보통 말하지만 내가 생각하기엔 상태값에 따라 2개를 나눈거라 생각한다. 이진 탐색은 그 상태값을 high OR low 로 지정되었다. 즉, 1 ~ 100의 자연수 중에서 나는 27이란 숫자를 찾게 된다고 가정하자.

1. 탐색 범위를 지정한다. -> ( 첫 탐색 범위 : 1 ~ 100 )
2. 탐색 범위에서 mid 값이 data보다 큰 지 작은 지 본다. -> ( 탐색 범위 mid : 50 / data : 27 / result : 크다 )
   1. result : 크다 ) 탐색 범위 1 (low) ~49( mid - 1 = high ) 로 정한다.
   2. result : 작다 ) 탐색 범위 51(mid +1 = low) ~ high ( 100 ) 로 정한다.
3. 탐색 범위가 다시 정해지면 2번과 같이 다시 mid 값과 data값이 같을 때 까지 반복한다!

간단히 up&down게임 개념이라고 생각하면 좋겠다.

public class BinarySearch {
    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
        int targetNum = 7;

        //중간값 찾기
        int startIdx = 0;
        int endIdx = nums.length - 1;
        int targetIdx = -1;
        while (startIdx <= endIdx) {
            int midIdx = (startIdx + endIdx) / 2;
            //인덱스(시작점, 끝점) 옮기기

            if (nums[midIdx] == targetNum) {
                targetIdx = midIdx;
                break;
            }
            if (nums[midIdx] > targetNum) {
                endIdx = midIdx - 1;
            } else {
                startIdx = midIdx + 1;

            }

        }
        System.out.println(targetIdx);
    }
}

코드 결과는 이렇고 설명을 해보자면

        int startIdx = 0;
        int endIdx = nums.length - 1;
        int targetIdx = -1;

배열의 시작은 0 이므로 0 번부터 마지막 배열의 번호는 배열의 길이 -1 이 기때문에 저렇게 변수들을 설정하고 직관성을 위해 targetIdx를 -1로 설정했다.

        while (startIdx <= endIdx) {
            int midIdx = (startIdx + endIdx) / 2;
            //인덱스(시작점, 끝점) 옮기기

시작 인덱스와 마지막 인덱스는 같은 수가 없으므로 한번은 시작되고 마지막까지 가운데로 가서 만나면 굳이 한번 더 실행하지 않고 반복문을 멈추기위해 저렇게 놓고 int midIdx = (startIdx + endIdx) / 2;로 배열의 중앙인덱스를 정하여 세팅을 한다.

            if (nums[midIdx] == targetNum) {
                targetIdx = midIdx;
                break;
            }

그 이후 중앙인덱스를 넣어 중앙값과 타겟의 수와 비교해 같다면 바로 빠져나올 수 있게 브레이크문을 사용한다.

            if (nums[midIdx] > targetNum) {
                endIdx = midIdx - 1;
            } else {
                startIdx = midIdx + 1;
            }
        }

만약 위의 조건문에 맞지 않아 믿으로 내려오면 중앙값이 타겟 넘버보다 크다면 마지막 인덱스르 중앙안덱스보다 한단계 작은 인덱스를 사용한다 그 이유는 중앙값 인덱스는 이미 비교 했기 때문에 -1을 해주고 마지막 포인트로 정해준다. 그 이후 else문은 if문과 반대로 설정해주면 된다.

간단히 설명하자면 타겟넘버가 중앙값보다 크다면 시작 인덱스를 중앙 값으로 정하는데 +1 해주는 이유는 이미 중앙값은 비교를 하였으니 그 다음 인덱스부터 해야 되니까 +1로 정해준다.