[알고리즘] 순차 검색(Sequential Search) 과 이분 검색(Binary Search) +

순차검색에 대해 설명하시고 예제소스를 구현해보아라.

• 정렬되어있지 않은 배열의 처음부터 끝까지 단방향으로 비교하여 원하는 데이터를 찾아내는 알고리즘이다.
• 시간복잡도 : O(n)
• 장점 : 구현이 쉽고 단순하다
• 단점 : 배열의 크기가 크면 비효율적이다.

int sequentialSearch(int a[], int  length, int  target) 
{
	for (int i = 0; i < length; i++)
	{
		if (a[i] == target)
		{
			return i;
		}
	}
	return 0;
}

---

이분검색(Binary Search)에 대해 설명하시고 예제소스를 구현해보아라.

• 정렬되어있는 자료를 반씩 나누어 나머지 반만 검색하는 방식을 반복하여 자료를 찾는 검색(탐색)방법
• 시간 복잡도: O(log n)
• 장점 : 빠른 속도로 원하는 자료를 찾을 수 있다.

int BSearch(int arr[], int target) 
{
    int low = 0;
    int high = sizeof(arr)/sizeof(int)-1;
    int mid;

    while (low <= high) {
        mid = (low + high) / 2;

        if (arr[mid] == target)
        {
            return mid;
        }
        else if (arr[mid] > target)
        {
            high = mid - 1;
        }
        else
        {
            low = mid + 1;
        }
    }
    return -1;
}

---

재귀함수를 이용하여 피보나치 수열을 구현해보아라.

• 피보나치 수열이란 ? 처음 두 항은 1이고 세번째 항부터 이전 두 항의 합이 된다. ( 1,1,2,3,5,8... )
• 재귀함수란? 자기자신을 return 값으로 가지는 함수

int fibo(int num)
{
	if (num == 0)
	{
		return 0;
	}
	else if(num == 1)
	{
		return 1;
	}
	else
	{
		return fibo(num - 1) + fibo(num - 2);
	}
}

 

[출처 및 참고 사이트]

https://cjh5414.github.io/binary-search/

https://mainia.tistory.com/4409