[Algorithm] Binary Search(이진 탐색) Algorithm

🎯 목표 :  이진 탐색 알고리즘의 구조와 탐색 원리에 대한 이해

📒 Binary Search

📌 특징

• 이진 탐색을 하고자 하는 데이터는 정렬되어 있어야한다.
• 정렬된 데이터들을 절반을 나눠 분할 정복 기법으로 특정한 값을 찾아낸다.
• 단계별 탐색 구조

1. 정렬된 배열의 가장 중간 인덱스 값을 찾는다.
2. 찾으려고 하는 값이 중간 인덱스 값이라면 탐색종료 그렇지 않다면 탐색 진행.
3. 찾으려고 하는 값이 중간 인덱스 값보다 큰지, 작은지 확인한다.
4. 해당하는 부분을 제외한 나머지 영역은 탐색 범위에서 제외한다.
5. 해당하는 부분에서 1. 단계부터 반복 탐색한다.

---

📌 구현

• 설명은 주석 참조

    public static int binarySearch(int[] arr, int key){
        // 탐색할 구간의 제일 처음 인덱스값 저장
        int pre = 0;
        // 탐색할 구간의 제일 끝 인덱스값 저장
        int end = arr.length-1;
        // pre 값이 end 값보다 커지면 종료.
        while (pre<=end) {
            // 탐색할 구간의 중간 인덱스값 저장.
            int center = (pre+end)/2;
            // 중간 인덱스값을 가진 요소가 key 같다면 해당 인덱스 반환 후 종료
            if(arr[center]==key){
                return center;
            // 중간 인덱스 값을 가진 요소가 key 값보다 작다면,
            }else if (arr[center]<key){
                // 다음 탐색할 구간의 제일 처음 인덱스 값을 중간 인덱스 값 +1로 저장.
                pre = center+1;
                // 중간 인덱스 값을 가진 요소가 key 값보다 크다면,
                // 다음 탐색할 구간의 제일 마지막 인덱스를 중간 인덱스 값 -1로 저장.
            }else end = center-1;
        }
        // 찾지 못했다면 -1 반환
        return -1;
    }

• 위와 같은 같은 원리의 재귀 호출로 구현

    public static int binarySearchRecursive(int[] arr, int key, int pre, int end) {
        // pre 탐색할 구간의 제일 처음 인덱스 값 저장.
        // end 탐색할 구간의 제일 마지막 인덱스 값 저장.
        if (pre > end)
            return -1;

        int center = (pre + end) / 2;
        if (arr[center] == key)
            return center;
        else if (arr[center] > key)
            return binarySearchRecursive(arr, key, pre, center-1);
        else
            return binarySearchRecursive(arr, key, center+1, end);
    }

---

📌 시간 복잡도

• n개 크기의 배열에서 한번 반복할때 마다 탐색할 구간이 반으로 줄어든다.
• n -> n/2 -> n/4 -> n/8 .....1에 가깝게 될것이고 log n이 된다.
• 이진 탐색의 시간 복잡도는 O(log n)이다.