이분 탐색

이분 탐색이란?

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

이분 탐색 방법

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

• 배열의 가운데 요소의 인덱스를 pivot으로 정합니다.

• arr[pivot]의 값이 찾고자 하는 값과 같다면 탐색을 종료합니다.

• arr[pivot]의 값이 찾고자 하는 값보다 작다면 pivot ~ right 사이를 탐색합니다.

• arr[pivot]의 값이 찾고자 하는 값보다 크다면 left ~ pivot 사이를 탐색합니다.

시간 복잡도

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

이분 탐색 구현 코드(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