이진 탐색 알고리즘

이진 탐색

이진 탐색이란 이미 정렬된 원소의 나열에서, 어떤 특정 자료를 찾기 위해 검색 범위를 절반으로 줄여가는 검색 알고리즘입니다.

💡 이진 탐색 과정

1) 가운데 위치의 원소를 고르고 비교한다.찾는 원소가 일치한다면 검색에 성공한다.
2) 찾는 원소보다 값이 크다면 왼쪽 절반을 다음 검색 대상으로 선택한다.
3) 찾는 원소보다 값이 작다면 오른쪽 절반을 다음 검색 대상으로 선택한다.
4) 찾는 원소를 만나거나, 찾을 수 있는 범위가 사라졌을 때 검색을 종료한다. 

이진 탐색 gif를 통해 이해하기

이진 탐색 시간복잡도

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

최선의 경우는 첫 루프에서 원하는 값을 찾은 경우입니다. 이럴 경우 O(1)의 시간복잡도를 가지게 됩니다. 그 외의 경우에는 탐색할 범위가 대략 절반씩 줄어들기때문에 O(log N)의 시간복잡도를 가집니다.

이진 탐색 장단점

✅ 장점

• 이진 탐색 알고리즘의 장점선형 탐색과 비교하여 탐색 시간이 빠르다. (선형 탐색의 경우 시간 복잡도는 T(n) = θ(n)이다. )

✅ 단점

• 이진 탐색 알고리즘의 단점정렬된 리스트에서만 사용될 수 있다.

이진 탐색 실습

public class BinarySearch {
    public int binarySearch(int[] arr, int target) {
        // 검색범위를 한정하는 left와 right
        int left = 0;
        int right = arr.length - 1;

        // 왼쪽 index가 오른쪽 인덱스보다 커지면 발견 실패
        while (left <= right) {
            // 현재 가운데 원소를 검색 대상과 비교
            int mid = left + (right - left) / 2;

            // 가운데서 발견: 검색 성공
            if (arr[mid] == target) return mid;
                // 찾는 숫자보다 지금 숫자가 작으면
                // mid 기준 오른쪽 구간을 대상으로 선정
            else if (arr[mid] < target) left = mid + 1;
                // 찾는 숫자보다 지금 숫자가 크면
                // mid 기준 왼쪽 구간을 대상으로 선정
            else right = mid - 1;
        }

        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        int target = 6;
        int index = new BinarySearch().binarySearch(arr, target);

        if (index != -1) {
            System.out.println(index);
        } else {
            System.out.println("탐색 실패");
        }
    }
}

출력 결과

5