[Extra] 순차탐색 이진탐색

순차탐색(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)

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

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