이진 탐색 (Binary Search)

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

배열이 정렬되어 있는 상태에서 사용할 수 있는 탐색 알고리즘이다.

1. 배열의 first index과 last index을 2로 나누어 middle index를 찾고 middle index의 배열 값과 타겟의 값을 비교하여 일치하면 찾기 종료.

2. 배열의 값이 타겟보다 크면 last index를 middle index-1로 설정.

3. 배열의 값이 타겟보다 작으면 firtst index를 middle index+1로 설정.

#include <stdio.h> int Binary_Search(int *arr, int num, int len) {     int first=0;     int last=len;     int mid;     while(first<=last)     {         mid = (first+last)/2;         if(arr[mid] == num)         {             return mid;         }         else         {             if(arr[mid] > num)             {                 last = mid-1;             }             else             {                 first = mid+1;             }         }     }     return -1; } int main() {     int num_arr[9] = {1,3,4,7,9,11,13,15,22};     int len = (sizeof(num_arr)/sizeof(num_arr[0]))-1;     int index = Binary_Search(num_arr,4,len);     if(index >= 0)     {         printf("index = %d\n",index);     }     else     {         printf("not found\n");     }     return 0; }