[강의] 11월 26일 수업정리

오늘은 이진 검색 알고리즘에 대한 수업을 들었다.

 

1. 이진 검색 알고리즘

오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다.

처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다.

 

이진 검색은 정렬된 리스트에서만 사용할 수 있다는 단점이 존재하지만, 검색이 반복될 때마다 검색 범위가 절반으로 줄기 떄문에 속도가 빠르다는 장점이 있다 ( log n )

 

 

1.1 포인터와 길이를 이용하여 이진 검색 알고리즘 

#include <iostream>

int main()
{
	int arData[40]{};
	int nData{};
	for (int i = 0; i < 40; i++)
	{
		arData[i] = i * 2;
	}

	scanf_s("%d", &nData);

	int* pData = arData;
	int nLength = 40;
	int nFindIndex = nLength / 2;
	int* pResult = pData + nFindIndex;

	while (nLength > 0 && pData[nFindIndex] != nData)
	{
		if (pData[nFindIndex] > nData)
			nLength = nFindIndex;
		else if (pData[nFindIndex] < nData)
		{
			pData = pData + nFindIndex + 1;
			nLength = nLength - (nFindIndex + 1);
		}
		nFindIndex = nLength / 2;
		pResult = pData + nFindIndex;
	}

	if (nLength <= 0)
		printf("못 찾았다\n");
	else
	{
		printf("%d ", *pResult);
		printf("index : %d\n", pResult - arData);
	}
}