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

} 


저작자표시 비영리 변경금지

'프로그래밍 > 알고리즘' 카테고리의 다른 글

하노이 타워  (0) 2014.02.13
재귀적 이진 탐색 알고리즘  (0) 2014.02.11
재귀적 팩토리얼 구현  (0) 2014.02.10
1+(1+2)+(1+2+3)+(1+2+3+4)+(1+2+3+4+5)의 결과를 구하는 알고리즘  (0) 2013.02.17 
1+(1+2)+(1+2+3)+(1+2+3+4)+(1+2+3+4+5)의 결과를 구하는 알고리즘

너무 오랜만에 코딩을 했다. 감을 익히기 위해 간단한 알고리즘 문제를 풀어봤다. 그.러.나.

#include <stdio.h>

void main()
{
int cnt, sum, rst, i;
rst=0; cnt=1; 

while(cnt<6)
{
sum=0;
for(i=1;i<cnt+1;i++)
{
  sum = sum + i;
}
cnt++; 
rst = rst+sum;
}
printf("%d",rst);
}


원래는 순서도 문제인데 문제만 보고 위와 같이 코딩을 했다. 답안 순서도를 보니 내 코드가 정말 저질이라는 것을 깨달았다.


답안 순서도를 보고 코드화 한 것이 아래 코드이다. 깔끔하다. 열심히 하자.


#include <stdio.h>

void main()
{
int cnt=0, sum=0, rst=0;

while(cnt<5)
{
cnt = cnt + 1;
sum = sum + cnt;
rst = rst + sum;
}
printf("%d",rst);
}


저작자표시 비영리 동일조건

'프로그래밍 > 알고리즘' 카테고리의 다른 글

하노이 타워  (0) 2014.02.13
재귀적 이진 탐색 알고리즘  (0) 2014.02.11
재귀적 팩토리얼 구현  (0) 2014.02.10
이진 탐색 (Binary Search)  (0) 2014.02.06

+ Recent posts

티스토리툴바