'이진탐색'에 해당되는 글 2건

  1. 2011.05.17 binary search - Java
  2. 2011.05.16 binary search - c
Computer Science/Algorithm2011. 5. 17. 20:50

binary search - Java

java로 이진탐색을 구현했는데 익숙해서인지 금방 끝났다. 새로운 패키지 만들기 귀찮아서 JUnit 으로 메소드를 생성했다.

@Test

public void main()
{
int n = 10;
int x[] = scaffolding(n);
int k = 70;
int result = binarySearch(x, n, k);
System.out.println(result);
}

public int[] scaffolding(int n)
{
int x[] = new int[n];
for(int i = 0; i < n; ++i)
x[i] = i * 10;
return x;
}

public int binarySearch(int[] x, int n, int k)
{
int l = 0; int u = n - 1; int m;
while(true) {
m = (l + u) / 2;
if(l > u)
return -1;
if(x[m] == k)
return m;
else if (x[m] > k)
u = m - 1;
else if (x[m] < k)
l = m + 1;
}
}


저작자표시

'Computer Science > Algorithm' 카테고리의 다른 글

insertion sort - c  (0) 2011.05.28
insertion sort - Java  (0) 2011.05.26
binary search - c  (0) 2011.05.16
반전 알고리즘  (0) 2011.05.12
도형 내부 채우기  (0) 2011.05.11
Posted by 준피
Computer Science/Algorithm2011. 5. 16. 21:24

binary search - c

c로 이진탐색을 구현해봤다. 오랜만에 쓴 포인터 덕에 고생좀 했다.

#include <stdio.h>
#include <malloc.h>

int binarysearch(int *x, int k, int n);
int* scaffolding(int n);

int main(){
    int n; int k; int *x;
    
    printf("\n배열 크기 : ");
    scanf("%d", &n);
    x = scaffolding(n);

    printf("\n찾고싶은 수 : ");
    scanf("%d", &k);

    int result = binarysearch(x, k, n);
    printf("\nresult : %d\n\n", result);
    
    return 0;
}

int* scaffolding(int n) {
    int *x; int i;

    x = (int *)malloc(n * sizeof(int));
    for(i = 0; i < n; ++i)
        x[i] = i * 10;
    
    return x;
}

int binarysearch(int *x, int k, int n) {
    int l = 0; int u = n-1; int m;

    while(1) {
        m = (l+u) / 2;

        if(l > u)
            return -1;

        if(x[m] == k) 
            return m;
        else if(x[m] > k)
            u = m-1;
        else if(x[m] < k)
            l = m+1;
    }
}

 


저작자표시

'Computer Science > Algorithm' 카테고리의 다른 글

insertion sort - c  (0) 2011.05.28
insertion sort - Java  (0) 2011.05.26
binary search - Java  (0) 2011.05.17
반전 알고리즘  (0) 2011.05.12
도형 내부 채우기  (0) 2011.05.11
Posted by 준피

티스토리툴바