[알고리즘] 이분 탐색

이분 탐색

 탐색 기법중에 하나로 원하는 탐색범위를 두 부분으로 분할해서 찾는 방식입니다. 그렇기에 원래의 전부를 탐색하는 탐색 속도에 비해 빠릅니다. 이분 탐색을 하는 방법은 left , right , mid 값으로 탐색하는 것입니다. mid의 값은 (left + right)/2 으로 잡아주고 우리가 검색하고자 하는 값과 mid 값을 비교합니다. 순서로 말하자면

1.이분 탐색을 하고자 할 때 이미 정렬이 되어있어야 합니다.

2. left, right로 미드값을 잡아줍니다.

3. mid 값과 구하고자 하는 값을 비교 합니다.

4. 비교할시 mid 값보다 구하고자 하는 값이 높으면 left를 mid+1로 만들어주고 낮으면 right를 mid-1로 만들어 줍니다. 

5. left > right 가 될때까지 1~3번을 반복해서 구하고자 하는 값을 찾습니다.

 이렇게 검색을 하면 전체를 검색하는 경우인 시간복잡도가 O( n ) 인거에 비해서 O( log(n) ) 으로 적다고 합니다. 이분 탐색의 예는 아래 그림으로 보여드리겠습니다.

코드

 정해진 배열에서 우리가 찾고자 하는 수가 배열의 몇번째에 있는지 탐색하는 간략화된 코드입니다. 

#include <stdio.h>
 
 
int main(void){
 
    int findN;
    int result = 0;
    //처음int는 다음 정점 마지막 int 값어치
 
    int A[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 15 };
 
    scanf("%d", &findN);
    int left = 0, right =  9;
 
 
    while (left <= right){
 
        int mid = (left + right) / 2;
        if (A[mid] > findN)
            right = mid - 1;
        else if (A[mid] < findN)
            left = mid + 1;
        else
        {
            result = mid;
            break;
        }
 
    }
 
    printf("%d\n", result);
 
    return 0;
}