[자료구조] 이진탐색

이진탐색

이진탐색의 개념

• 정렬된 배열에서 특정 값을 찾는 알고리즘
• 이분 탐색이라고도 함
• 탐색 범위를 절반씩 나누어 찾는 값을 포함하는 범위를 좁혀가는 방식
• 주로 배열의 인덱스를 기준으로 배열 내의 값을 탐색

 

이진탐색 방법

이미지 출처 : https://adjh54.tistory.com/187

 

1. 배열의 중간에 있는 임의의 값(중간 값)을 선택
2. 선택한 값을 찾고자 하는 값과 비교
3. 선택한 임의의 값이 찾고자 하는 값보다 작으면 임의의 값 기준 좌측의 데이터들을, 크면 우측의 데이터들을 대상으로 다시 탐색
4. 해당 값을 찾을 때까지 반복

이진탐색의 장점

• 검색 속도가 빠름
• 검색이 반복될 때마다 검색 범위가 절반으로 줄어듦
• 검색 대상의 크기와 상관없이 빠른 검색 속도를 제공
• 대량의 데이터를 다루는 알고리즘에서 많이 사용
• O(logn)의 검색 속도 보장

 

이진탐색의 단점

• 배열이나 이진 탐색 트리와 같이 정렬된 구조에서만 사용 가능
• 정렬되어 있지 않은 경우 사용 불가능
• 탐색을 위한 추가적인 메모리를 사용하지 않기에 검색 대상의 생성, 수정하는 경우 탐색 시간이 길어질 수 있음

 

시간복잡도

• 최선 : O(1)
• 평균 : O(log n)
• 최악 : O(log n)

 

구현

1. 반복문

    public boolean BinarySearch(int[] arr, int n) {
        int left = 0;
        int right = arr.length - 1;
        int middle;

        while (left <= right) {
            middle = (left + right) / 2;
            if (arr[middle] < n) {
                left = middle + 1;
            }
            else if (arr[middle] > n) {
                right = middle - 1;
            }
            else {
                return true;
            }
        }
        return false;
    }

 

2. 재귀

    public boolean BinarySearch(int[] arr, int n, int left, int right) {
        int middle;

        if(left > right) {
            return false;
        }

        middle = (left + right) / 2;

        if (arr[middle] < n) {
                return BinarySearch(arr, n, middle +1, right);
        }
        else if (arr[middle] > n) {
                return BinarySearch(arr, n, left, middle - 1);
        }
        else { 
                return true;
        }
    }