Binary Search

#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 찾음.