2진탐색
int binarySearch(int x, int c, int* list, int* cnt)
{
*cnt+=3;
int mid, left = 0, right = c * 10 - 1, location = -1;
<?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" /><o:p></o:p>
while(left < right)
{
*cnt+=2;
mid = (left + right) / 2;
<o:p></o:p>
*cnt+=2;
if(x == list[mid])
{
*cnt+=2;
location = mid;
break;
}
else if(x > list[mid])
{
*cnt+=1;
left = mid + 1;
}
else
{
*cnt+=1;
right = mid;
}
}
<o:p></o:p>
*cnt+=1;
return location;
}
<선형탐색>
int linearSearch(int x, int c, int* list, int* cnt)
{
*cnt+=1;
int location = -1;
<o:p></o:p>
for(int i = 0; i < c * 10; i++)
{
*cnt+=2;
if(list[i] == x)
{
*cnt+=2;
location = i;
break;
}
else
{
*cnt+=1;
continue;
}
}
<o:p></o:p>
*cnt+=1;
return location;
}
이코드가 맞나요???
이코드 시간복잡도를 구할수도 있는건가요?ㅠㅠ
N, logN