[Algorithm] 1. Binary Search? 2 .Binary or SeqSearch ?

2011/03/14 - [Algorithms] - [Algorithm] 1. Binary Search? 2 .Binary or SeqSearch ? 2011/03/13 - [Algorithms] - [Algorithms] 1.Sequential, 2.Add Array, 알고리즘에 대해 2011/03/13 - [Algorithms] - [Algorithm]pseudo code란? 의사코드란?

1) Binary Search란?

n개가 들어있는 정렬된 배열 Array 에서 s값을 찾을 때 사용됩니다.

void binarySearch(개수,  배열,   찾고자하는 값,  위치 정보를 담을 값)

void binarySearch(int n,  const keytype S[],  type x, index & location)

{

index low,high,mid;

low =1;

high = n;

location = 0;

while(low <= high && location == 0)

{

mid = (low + high)/2;

if( x == S[mid])

location = mid;

else if(x < S[mid])

high = mid -1;

else

low = mid + 1;

}

}

2) Binary ? Sequential ?

순차 검색 ( Sequential Search )는  배열의 모든 값을 비교 하기 때문에  배열의 개수 ( n ) 번 비교를 한다

이진 검색 ( Binary Search ) 는 lgn + 1 만큼 비교를 한다.