이진탐색(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);
}