탐색 - 이진탐색법(Binary Search)

순차탐색법(Linear Search) 보다 훨씬 좋은 성능을 보이는 탐색법이다.

그러나 이진탐색법을 이용하기 위해선 "배열에 저장된 데이터는 정렬되어 있어야 한다"

 

다음의 배열에서 숫자 5의 인덱스를 구해보자.

int [] arr	index	0	1	2	3	4	5	6	7	8
	value	2	3	5	6	8	10	11	15	19

1. 배열의 가운데 숫자 arr[4] 가 3보다 크다.

  >> 숫자 5는 배열의 index가  0, 1, 2, 3 중에 하나 이다. 

2. 배열의 index 가 0~ 3 의 중간인 arr[1] 가 2 보다 작다 

 >> 숫자 5 는 배열의 index 가 2, 3, 중에 하나이다.

3. 배열 index 가 2~ 3 의 중간인 arr[2] 의 값이 5이다!!

 

이러한 과정으로

배열에 길이가 n일때

1, 배열의 인덱스가 n/2인 값과 찾는 값 확인

  >> 배열의 인덱스가 n/2인 값보다 크다  > 배열의 인덱스가 n/2+1 ~ n  사이에 찾는 수가 있다.

  >> 배열의 인덱스가 n/2인 값보다 작다다  > 배열의 인덱스가 0 ~ n/2  사이에 찾는 수가 있다.

>>> 반복~ 이를 재귀 함수로도 짤 수 있을 것 같아 두가지 방식으로 구현 해보았다.

 

0. 구현

public class Search {
    /**
     * 이진 탐색 
     * @param array
     * @param find
     * @return
     */
    int binary(int [] array, int find){
        int startIdx = 0;
        int lastIdx = array.length-1;
        int centerIdx = (lastIdx + startIdx)/2;

        while(array[centerIdx] != find){

            if(startIdx>lastIdx){
                return -1;
            }

            if(array[centerIdx] < find){
                startIdx = centerIdx +1;
            }else{
                lastIdx = centerIdx -1;
            }

            centerIdx = (lastIdx + startIdx)/2;
        }


        return centerIdx;
    }
    
    
    /**
     * 이진탐색 재귀
     *
     * @param array
     * @param startIdx
     * @param lastIdx
     * @param find
     * @return
     */

    int binaryRecursive(int [] array, int startIdx, int lastIdx, int find){

        if(lastIdx - startIdx < 2){
            if(array[startIdx] == find){
                return startIdx;
            }else if(array[lastIdx] == find){
                return lastIdx;
            }else{
                return -1;
            }
        }

        if(array[startIdx+(lastIdx-startIdx)/2] >= find){

            return binaryRecursive(array, startIdx, startIdx+(lastIdx-startIdx)/2, find);
        }else{
            return binaryRecursive(array, startIdx+(lastIdx-startIdx)/2+1, lastIdx, find);

        }
    }
}