이분 탐색 (+Java)

1. 이분 탐색이란

이분 탐색아란 오름차순으로 정렬된 수열에서 원하는 값을 찾는 탐색 알고리즘입니다. 여기서 포인트는 정렬된 수열에서 가능하다는 것입니다!

 

2. 이분 탐색 방법

정렬된 배열에서 값을 찾는다는 가정 하에 아래의 과정을 반복하면 됩니다!

 

• 배열의 가운데 요소의 인덱스를 pivot으로 정합니다.
• arr[pivot]의 값이 찾고자 하는 값과 같다면 탐색을 종료합니다.
• arr[pivot]의 값이 찾고자 하는 값보다 작다면 pivot ~ right 사이를 탐색합니다.
• arr[pivot]의 값이 찾고자 하는 값보다 크다면 left ~ pivot 사이를 탐색합니다.

 

3. 시간 복잡도

이분 탐색의 시간 복잡도는 O(logN)으로 기본적인 선형 탐색보다 훨씬 빠르게 탐색을 할 수 있습니다.

 

4. 이분 탐색 구현 코드(Java)

public class Main {    
    public static void main(String[] args) {
        int[] arr = {5, 12, 14, 33, 54, 66, 72, 75, 88};
        int target = 66;

        binary_search(arr, target);
    }

    static void binary_search(int[] arr, int target) {
        int start = 0;
        int end = arr.length - 1;
        int pivot = (start + end) / 2;
        boolean flag = false;

        while(start <= end) {
            if(arr[pivot] == target) {
                flag = true;
                System.out.println(target + "은 " + pivot + " 번 인덱스 위치에 있습니다.");
                break;
            }
            if(arr[pivot] > target) end = pivot-1;
            else start = pivot+1;

            pivot = (start + end) / 2;
        }

        if(!flag) {
            System.out.println(target + "은 배열 내에 존재하지 않는 값입니다.");
        }
    }
}

 

 

참고
https://velog.io/@gkscodus11/%EC%9D%B4%EB%B6%84-%ED%83%90%EC%83%89Binary-Search
https://lazyren.github.io/devlog/binray-search.html