Extra

[Extra] 순차탐색 이진탐색

호호호호히히히히 2018. 3. 16. 13:42
728x90
반응형



순차탐색(Sequential search)


선형 탐색(Linear search)이라고도함

전제조건 : 없음 (정렬되지 않은 리스트여도됨)

방법 : 찾을 숫자를 처음부터 나올때 까지 비교함



ex) 1-20중 숫자 고르기 (19)



source)

int j = [찾을 숫자]


int[] arrList;


for(int i = 0; i < arrList.length; i++)

{

if (arrList[i] == j)

{

return i;

}

}



빅오 표기법 : O(N)



이진탐색 (Binary search)


전제조건 : 정렬된 데이터

방법 : 정렬된 데이터 집합이분화하면서 탐색하는 방법 (관계 없는 1/2을 제외시킴)


ex) 1-20중 숫자 고르기 (19)


빅오 표기법 : O(log N)



* 반씩 잘라서 찾아나가는것 "이진탐색"

* 용량이 많아질 경우 눈에 띄게 연산 횟수 차이가 나게됨

반응형