[Java] 이진탐색(Binary Search)

이진탐색(Binary Search)

이진탐색(BinarySearch) 알고리즘은 쉽게 말해서 탐색의 대상을 반으로 분할하고 분할하고, 분할해서 원하는 값을 찾는 탐색 방법입니다.  

반으로 분할하는 과정이 있기에 순차탐색(SequentialSearch) 알고리즘에 비해 좋은 성능을 보입니다.

이 알고리즘을 적용하기 위해서는 "배열(리스트) 에 저장된 데이터는 정렬되어 있어야 한다." 즉, 정렬되어 있진 데이터가 아니면 적용이 불가능하다 는 뜻입니다.

이유는 정렬과정에서 중앙 값을 확인 하기 위해 분할을 하는데 이때, 정렬이 되어있지 않으면 분할의 의미가 없어지기 때문입니다.

다음 그림을 보면,

1. '17' 을 찾는다고 가정을 하자.

2. 배열의 인덱스 시작과 끝 값을 더하여 그 결과를 2 로 나눈다. ==> (0+8)/2 = 4

     ( 이 때 나머지는 버리고 몫을 기준으로 생각한다. )

3. 배열의 인덱스 4 는 10, 10 은 '17' 보다 작으므로

4. 10 왼편의 있는 값들을 제외한다.

5. 다시 배열의 인덱스의 시작과 끝 값을 더하여 그 결과를 2로 나눈다. ==> (5+8)/2 = 6

6. 배열의 인덱스 6 은 24, 24 는 '17' 보다 크므로
7. 24 오른편의 있는 값들을 제외한다.

8. 남은 배열의 인덱스는 5 는 15
9. 15 는 찾을 려는 '17' 과 다른 값이므로 

10. 이 배열에는 '17' 이 존재 하지 않으므로 '-1' 을 반환

활용예제


public class BinarySearcher {

        public int search(int[] arr, int target) {

                int first = 0;
                int last = arr.length;
                int mid;

                while (first <= last) {

                        mid = (first + last) / 2;

                        if (target == arr[mid]) {

                                return mid;
                        }

                        else {

                                if (target < arr[mid])
                                        
                                        last = mid - 1;

                                else

                                        first = mid + 1;
                        }
                        // if target is not existed,
                        // not occur reversal of the first and last
                }
                
                return -1;
                // when target is not existed
        }
}