이진 탐색(Binary Search)

---

1. 이진 탐색(Binary Search)

이진 탐색은 값이 정렬 되어 있는 상태에서 중앙 값을 이용해서 찾고자 하는 데이터의 위치를 탐색하는 알고리즘 입니다. 전체 탐색 범위(첫번째 인덱스, 마지막 인덱스)와 중앙 인덱스 알고 있다면, 중앙 인덱스의 값과 찾고자 하는 데이터의 값을 비교 해서, 더 작다면 왼쪽만 탐색, 더 크다면 오른쪽만 탐색 합니다. 따라서 우리는 3가지 변수를 알고 있어야 합니다.

첫번째 인덱스 : head

마지막 인덱스 : tail

중앙 인덱스 : mid = (head + tail) / 2

여기서, 중앙 인덱스의 나머지 값은 버리고, 몫만 사용 합니다.

 

 

2. 이진 탐색(Binary Search) 순서

 

위 그림과 같이, 찾고자 하는 target 값은 9 입니다.

 

(target < array[mid]) 라면, tail = mid - 1 업데이트

(target > array[mid]) 라면, head = mid + 1 업데이트

(target == array[mid]) 면, mid를 반환해 줍니다.

 

 

 

이진 탐색은 탐색 범위를 반씩 줄여 갈수 있다는 점에서 시간 복잡도 : O(logN) 입니다. 탐색 범위가 크고 데이터의 정렬 기준이 정해져 있는 문제에서 이진 탐색(Binary Search)을 고려해 볼수 있을거 같습니다.

 

 

3. Java 소스 코드(재귀함수, 반복문)

 

public class BinarySearch {

    public static final int ERROR_NUM = -999999;

    /*
     * 이진탐색 구현
     * 전체 배열이 주어지고
     * 타겟 값이 주어졌을때
     * 데이터는 정렬되어 있다고 가정
     */
     // 재귀함수를 이용한 이진 탐색
    public int searchAsRecursion(int[] array, int target, int head, int tail) {
        // 시작 인덱스가 끝 인덱스 보다 크면 마이너스 값 리턴
        if (head > tail) return ERROR_NUM;

        // 중간값을 구함
        int mid = (head + tail) / 2;

        if (target == array[mid])
            return mid;
        else if (target < array[mid])
            return searchAsRecursion(array, target, head, mid - 1);
        else
            return searchAsRecursion(array, target, mid + 1, tail);
    }

    // 반복문을 이용한 이진 탐색
    public int searchAsIteration(int[] array, int target, int head, int tail) {
        while(head <= tail){
            int mid = (head + tail) / 2;
            if (target == array[mid])
                return mid;
            else if(target < array[mid])
                tail = mid - 1;
            else
                head = mid + 1;
        }
        return ERROR_NUM;
    }
}

 

이진 탐색(Binary Search) 알고리즘은 재귀 함수와 반복문을 이용해서 구현 할 수 있습니다.