이진탐색이란?

개념) 데이터가 정렬되어 있는 배열에서 내가 원하는 특정한 데이터를 알아내는 알고리즘 

 

방법)

1. 찾고자 하는 데이터 : A 라고 할떄 배열의 중간에 임의의 값을 선택해 A와 비교한다. 이때 배열을 오름차순으로 정리해준다. (주로 qsort알고리즘 이용)

2. A가 중간값보다 작을 경우 -> 중간값 기준 좌측 데이터를  대상으로 비교한다.

    A가 중간값보다 클 경우     -> 중간값 기준 우측 데이터를 대상으로 비교한다.

3. 좌측기준으로 데이터를 비교 할때 위의 과정과 똑같이 새로운 중간값을 정해 그값을 A와 비교한다. 우측데이터도 동일하다.

4. 이런식으로 찾고자 하는 데이터 A를 찾을떄까지 반복한다.

 

예시)

 배열  : {10, 3,  5, 14, 1, 6, 9} 

오름차순 배열 : {1, 3,  5, 6, 9, 10, 14}

찾고자 하는 데이터 :  14

1. 중간값 6 이므로 14과 비교한다.

2. 6 < 14 이므로 우측데이터

3. 우측데이터 {9, 10, 14}  중간값 10

4. 10 < 14 이므로 우측데이터

5 . 우측데이터 {14} 밖에 없기 때문에 우측데이터 == 14 이므로 대상을 찾는다.

 

구현)

int BSearch(int arr[], int target) 
{
    int low = 0;
    int high = arr.length - 1;
    int mid;

    while(low <= high) 
    {
        mid = (low + high) / 2;

        if (arr[mid] == target)
            return mid;
        else if (arr[mid] > target)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return -1;
}