이진 탐색(정렬) & #include <cmath>_pow()

이진 탐색 소스코드.

이진 탐색을 하기 위해서는 정렬 필요 

why 오름차순 배열에서 반 잘라서 같으면 탐색 성공 크면 다시 오른쪽의 반만 아니면 반대로 진행

시간 복잡도 : O(logN) -> 빠름.

->  sort(arr1, arr1+n);

나는 동적할당을 자주 사용하니까 다음과 같은 형식으로 처음과 끝을 지정해주었다.

백준 1009번 문제를 푸는데 시간제한이 떠서 개념만 복습하고 직접 구현해봤다. 

알고리즘 수업을 들은게 벌써 2년전이니까..  가물가물했어도 성공했다.

 

탐색, 연산, 정렬을 재귀로 수행하게 되면 공간복잡도가 시간복잡도인 O(log N)을 더 차지하게 된다.

재귀로 수행할 경우 스택에 시간복잡도 만큼 호출을 하게 되어 공간을 더 차지하게 된다고 한다.

-나무위키 참조 (유클리드 호제법)-

 

int bineary(int *arr, int target, int first, int last) {

    

    if(first > last)

        return 0;

    

    else {

        int mid = (first + last)/2;

        

        if(arr[mid] == target)

            return 1;

        else if(arr[mid] > target)

            return bineary(arr, target, first,mid-1);

        else

            return bineary(arr, target, mid+1,last);

        

    }

}

 

이진 탐색을 재귀가 아닌 반복문으로 할 경우.

 

#Pow() 와 exp()

파이썬에서는 exp()를 

C++ 에서는 cmath 라이브러리의 pow()를 사용.

 

제곱근 (Square root)는 둘 다 sqrt() 사용.

 

 

        

    }