알고리즘 - 이진탐색(Binary Search)

이진탐색(Binary Search), K찾기

- 오름차순으로 데이터를 정렬한다.

- 중간 숫자와 K비교한 후 같으면 탐색 성공

- K가 작으면 앞부분 반에서 같은 방법으로 K를 찾고

- K가 크면 뒷부분 반에서 같은 방법으로 K를 찾는다.

 

값이 보다 크다면 mid + 1 ~ high / 2

값이 보다 작다면 low ~ mid - 1 / 2

 

 

void binarysearch(int a[], int high, int target){
    int low = 0, mid; //첫 최솟값은 0
    while (low <= high) {
        mid = (low + high) / 2; //중간값은 최소와 최대를 합친것의 반. 못찾을때 마다 업데이트
        if(target == a[mid]){   // 타겟을 찾았을 때.
            printf("\n%d의 인덱스는 %d\n", target, mid);
            return;
        }
        else if(target < a[mid]){ // 목표가 반보다 작다면
            high = mid - 1; // low ~ mid - 1
        }else{	//목표가 반보다 크다면
            low = mid + 1;  // mid + 1 ~ high
        }
    }
    printf("\n%d는 없습니다.\n",target);
}