#include<stdio.h>
#define LEN 7
int BinarySearch(int* ar, int key) {
int up, down, mid;
down = 0; // 처음
up = LEN - 1; // 끝
for (;;) { // 무한루프
// 중앙 원소
mid = (up + down) / 2;
if (ar[mid] == key) return mid;
// 목표 값이 원소보다 작다면 왼쪽 반 수행
if (ar[mid] > key) {
up = mid - 1; // 왼쪽으로
}
else {
down = mid + 1; // 오른쪽으로
}
// 검색이 끝남
if (up < down) {
return -1;
}
}
}
int main() {
int tc, key, arr[LEN] = { 0, }; // 테스트 케이스 수, 찾는 숫자, 배열(오름차순)
scanf_s("%d", &tc); // 테스트 케이스 수 입력
for (int t=0; t < tc; t++) {
for (int i=0; i < LEN; i++)
scanf_s("%d", &arr[i]); // 배열 입력
scanf_s("%d", &key); // 찾을 숫자 입력
int k = BinarySearch(arr, key);
printf("%d %d", tc, k);
}
}
이진 탐색은 정렬된 배열에서 가운데 원소를 기준으로 찾는 숫자 key와 비교하며 탐색을 한다.
가운데 원소 ar[mid]가 key보다 크면 왼쪽, ar[mid]가 key보다 작으면 오른쪽으로 탐색을 한다.
1(key) | 2 | 3 | 4(mid) | 5 | 6 | 7 |
1<4이므로 2를 mid로 설정한다. 왼쪽 이동
1(key) | 2(mid) | 3 | 4 | 5 | 6 | 7 |
1<2이므로 왼쪽 이동하고 key 찾음.
반응형
'Computer science > Algorithm' 카테고리의 다른 글
문자의 표현 (0) | 2021.03.02 |
---|---|
Selection Sort (0) | 2021.02.24 |
Sequential Search (0) | 2021.02.22 |
Counting Sort (0) | 2021.02.16 |
Bubble-Sort (0) | 2021.02.16 |